模板
(Problem:) 多个模式串匹配文本串,求能合法匹配的个数
(limit:1 leq n leq 10^6)
(templete:)(Luogu P3808)
(Code)
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1e6 + 5;
int n , tr[N][26] , tot , tag[N * 26] , q[N * 26] , fail[N * 26];
char s[N];
void insert()
{
int len = strlen(s) , u = 0;
for(register int i = 0; i < len; i++)
{
int ch = s[i] - 'a';
if (!tr[u][ch]) tr[u][ch] = ++tot;
u = tr[u][ch];
}
++tag[u];
}
void get_fail()
{
int h = 0 , t = 0;
for(register int i = 0; i < 26; i++) if (tr[0][i]) q[++t] = tr[0][i];
while (h < t)
{
int now = q[++h];
for(register int i = 0; i < 26; i++)
{
if (tr[now][i]) fail[tr[now][i]] = tr[fail[now]][i] , q[++t] = tr[now][i];
else tr[now][i] = tr[fail[now]][i];
}
}
}
int query()
{
int len = strlen(s) , u = 0 , res = 0;
for(register int i = 0; i < len; i++)
{
int ch = s[i] - 'a';
u = tr[u][ch];
int v = u;
while (v && tag[v] != -1) res += tag[v] , tag[v] = -1 , v = fail[v];
}
return res;
}
int main()
{
scanf("%d" , &n);
for(register int i = 1; i <= n; i++)
{
scanf("%s" , s);
insert();
}
get_fail();
scanf("%s" , s);
printf("%d" , query());
}