采用字典树和KMP算法的思想,实现字符串的多模式匹配问题
#include <bits/stdc++.h>
#define io cin.tie(0), cout.tie(0), ios::sync_with_stdio(false)
#define LL long long
#define ULL unsigned long long
#define EPS 1e-7
#define INF 0x7fffffff
#define SUB -INF - 1
using namespace std;
const int N = 10005;
struct node
{
int son[26];
int end;
int fail;
} t[N];
int cnt = 1;
void Insert(char *s)
{
int now = 0;
for (int i = 0; s[i]; i++)
{
int ch = s[i] - 'a';
if (t[now].son[ch] == 0)
t[now].son[ch] = cnt++;
now = t[now].son[ch];
}
t[now].end++;
}
void getFail()
{
queue<int> q;
for (int i = 0; i < 26; i++)
if (t[0].son[i])
q.push(t[0].son[i]);
while (!q.empty())
{
int now = q.front();
q.pop();
for (int i = 0; i < 26; i++)
{
if (t[now].son[i])
{
t[t[now].son[i]].fail = t[t[now].fail].son[i];
q.push(t[now].son[i]);
}
else
t[now].son[i] = t[t[now].fail].son[i];
}
}
}
int query(char *s)
{
int ans = 0, now = 0;
for (int i = 0; s[i]; i++)
{
int ch = s[i] - 'a';
now = t[now].son[ch];
int tmp = now;
while (tmp && t[tmp].end != -1)
{
ans += t[tmp].end;
t[tmp].end = -1;
tmp = t[tmp].fail;
}
}
return ans;
}
char str[N];
int main()
{
int n;
scanf("%d", &n);
while (n--)
{
scanf("%s", str);
Insert(str);
}
getFail();
scanf("%s", str);
printf("%d\n", query(str));
return 0;
}