791
京东网上商城
AC自动机
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
using namespace std;
int T[400100][26] = {0};
int last[401000], f[410000], val[410000];
int sz = 0;
void _Insert(string s){
int u = 0;
for (int i = 0; s[i]; i++){
int c = s[i] - 'a';
if (!T[u][c]){
T[u][c] = ++sz;
val[sz] = 0;
}
u = T[u][c];
}
val[u] ++;
}
char s[1000100];
void build(){
queue<int> q;
for (int i = 0; i < 26; i++){
int u = T[0][i];
if (u){
f[u] = last[u] = 0;
q.push(u);
}
}
while (!q.empty()){
int h = q.front(); q.pop();
for (int i = 0; i < 26; i++){
int u = T[h][i], v = f[h];
if (!u){
T[h][i] = T[v][i];
continue;
}
q.push(u);
while (v && !T[v][i]) v = f[v];
f[u] = T[v][i];
last[u] = val[f[u]] ? f[u] : last[f[u]];
}
}
}
long long sum = 0;
void print(int j){
if (j){
sum += val[j];
val[j] = 0;
print(last[j]);
}
}
void aFind(){
int j = 0;
for (int i = 0; s[i]; i++){
int c = s[i] - 'a';
j = T[j][c];
if (val[j]) print(j);
else if (last[j]) print(last[j]);
}
}
int main(){
int t;
cin>>t;
while (t--){
int n; cin>>n;
memset(T, 0, sizeof(T));sz = 0;
memset(last, 0 ,sizeof(last));
memset(f, 0, sizeof (f));
memset(val, 0, sizeof(val));
for (int i = 0; i < n; i++){
string a;
cin>>a;
_Insert(a);
}
build();
scanf("%s", s);
sum = 0;
aFind();
printf("%d\n", sum);
}
}
最后更新：2017-08-23 08:02:18