首先容易根据给出的字符串建出trie树
对于查询（x,y），相当于对于y的每一个位置求出他的后缀是否包含x串
那么容易想到建立出ac自动机。
那么就是对于y串的每个位置，其能否通过fail到达x所在节点。
发现其实fail指针会构成一棵树，那么相当于统计在x节点下有多少点属于[......]
标签：ac自动机
2938: [Poi2000]病毒
考虑如果已经有了一个无限长的串，那么现在就是判断这个串能不能合法。
对于所有串建立ac自动机，那么显然如果一个点是病毒，其以后的点都是病毒，
并且如果一个点的fail是病毒，那么这个点也应该是病毒。
在ac自动机上跑，如果能一直不经过所有标记过的点（即为环）那么一定存在这个串。
c++代[......]
3172: [Tjoi2013]单词
直接套上ac自动机模板。
然后倒序扫一遍就好了。
c++代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
#include<bits/stdc++.h> #define rep(i,x,y) for(register int i = x ; i <= y; ++ i) #define repd(i,x,y) for(register int i = x ; i >= y; -- i) using namespace std; const int N = 1e6 + 500; char s[N]; int n,sz = 1,t[N][26],num[N],belong[N],fail[N]; int q[N]; inline void insert(char*s,int id) { int x = 1,len = strlen(s); rep(i,0,len - 1) { if(!t[x][s[i] - 'a']) t[x][s[i] - 'a'] = ++sz; x = t[x][s[i] - 'a'];++num[x]; } belong[id] = x; } inline void build_ac() { int st,en; q[st = en = 0] = 1; rep(i,0,25) t[0][i] = 1; while(st <= en) { int x = q[st++]; rep(i,0,25) if(t[x][i]) { int y = fail[x]; while(!t[y][i]) y = fail[y]; fail[t[x][i]] = t[y][i]; q[++en] = t[x][i]; } } repd(i,en,0) num[fail[q[i]]] += num[q[i]]; } int main() { scanf("%d",&n); rep(i,1,n) { scanf("%s",s); insert(s,i); } build_ac(); rep(i,1,n) printf("%d\n",num[belong[i]]); return 0; } |