AC自动机及KMP练习

好久都没敲过KMP和AC自动机了。以前只会敲个kuangbin牌板子套题。现在重新写了自己的板子加深了印象。并且刷了一些题来增加自己的理解。

KMP网上教程很多，但我的建议还是先看AC自动机（Trie图）的构造后再去理解。板子的话大家大同小异。

而AC自动机的构造则是推荐王贇的《Trie图的构建、活用与改进》。

前面的备用知识则是字典树。推荐董华星的《浅析字母树在信息学竞赛中的应用》。董聚聚不仅仅是介绍了字典树，包括一些常见的应用也有论述，介绍的挺详细的。

接下来就是刷题的部分了。

hdu 5880

Family View

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2660    Accepted Submission(s): 577


Problem Description
Steam is a digital distribution platform developed by Valve Corporation offering digital rights management (DRM), multiplayer gaming and social networking services. A family view can help you to prevent your children access to some content which are not suitable for them.

Take an MMORPG game as an example, given a sentence T, and a list of forbidden words {P}, your job is to use '*' to subsititute all the characters, which is a part of the substring matched with at least one forbidden word in the list (case-insensitive).

For example, T is: "I love Beijing's Tiananmen, the sun rises over Tiananmen. Our great leader Chairman Mao, he leades us marching on."

And {P} is: {"tiananmen", "eat"}

The result should be: "I love Beijing's *********, the sun rises over *********. Our gr*** leader Chairman Mao, he leades us marching on."
 
Input
The first line contains the number of test cases. For each test case:
The first line contains an integer n , represneting the size of the forbidden words list P . Each line of the next n lines contains a forbidden words Pi (1≤|Pi|≤1000000,∑|Pi|≤1000000) where Pi only contains lowercase letters.

The last line contains a string T (|T|≤1000000) .
 
Output
For each case output the sentence in a line.
 
Sample Input
1 3 trump ri o Donald John Trump (born June 14, 1946) is an American businessman, television personality, author, politician, and the Republican Party nominee for President of the United States in the 2016 election. He is chairman of The Trump Organization, which is the principal holding company for his real estate ventures and other business interests.
 
Sample Output
D*nald J*hn ***** (b*rn June 14, 1946) is an Ame**can businessman, televisi*n pers*nality, auth*r, p*litician, and the Republican Party n*minee f*r President *f the United States in the 2016 electi*n. He is chairman *f The ***** *rganizati*n, which is the p**ncipal h*lding c*mpany f*r his real estate ventures and *ther business interests.
 
Source
2016 ACM/ICPC Asia Regional Qingdao Online
 
 
裸题，把模式串构成Trie图然后在主串中匹配。Trie图中设置标记tag，若本身就是词尾节点则tag指向自己，否则指向该节点离他最近的词尾后缀节点。没有则指向根节点。接下来就转化为线段覆盖问题了。扫主串的时候扫到模式串对应的词头位置pos++，词尾pos--。接着求字符串pos前缀和，前缀和>0的部分赋’*’，然后输出字符串。
有两个版本，一个是刚开始按KMP的想法写的，稍微改改就能改成孩子兄弟链法：
  1 #include<cstdio>
  2 #include<iostream>
  3 #include<cstring>
  4 #include<queue>
  5 #define clr(x) memset(x,0,sizeof(x))
  6 #define clr_1(x) memset(x,-1,sizeof(x))
  7 #define INF 0x3f3f3f3f
  8 #define mod 1000000007
  9 #define LL long long
 10 #define next nexted
 11 using namespace std;
 12 const int N=1e6+100;
 13 const int type=26;
 14 struct node
 15 {
 16     int pre;
 17     int dep;
 18     int tag;
 19     int next[type];
 20 }trie[N];
 21 int tot;
 22 int pos[N];
 23 int newnode()
 24 {
 25    trie[++tot]=(node){};
 26     return tot;
 27 }
 28 void add(int root,char *s)
 29 {
 30     int len=strlen(s);
 31     int now=root;
 32     int p;
 33     for(int i=0;i<len;i++)
 34     {
 35         p=s[i]-'a';
 36         if(!trie[now].next[p])
 37         {
 38             trie[now].next[p]=newnode();
 39         }
 40         now=trie[now].next[p];
 41         trie[now].dep=i+1;
 42     }
 43     trie[now].tag=now;
 44 }
 45 void init()
 46 {
 47     tot=0;
 48     trie[0]=(node){};
 49     clr(pos);
 50     return ;
 51 }
 52 void getfail()
 53 {
 54     queue<int> que;
 55     int now,nowto,j;
 56     for(int i=0;i<type;i++)
 57         if(trie[0].next[i])
 58             que.push(trie[0].next[i]);
 59     while(!que.empty())
 60     {
 61         now=que.front();
 62         que.pop();
 63         for(int i=0;i<type;i++)
 64         {
 65             nowto=trie[now].next[i];
 66             if(nowto)
 67             {
 68                 que.push(nowto);
 69                 j=trie[now].pre;
 70                 while(j && !trie[j].next[i])
 71                     j=trie[j].pre;
 72                 trie[nowto].pre=trie[j].next[i];
 73                 if(trie[trie[j].next[i]].tag && !trie[nowto].tag)
 74                     trie[nowto].tag=trie[trie[j].next[i]].tag;
 75             }
 76         }
 77     }
 78     return ;
 79 }
 80 void acm(char *s)
 81 {
 82     int j=0,p,tmp;
 83     int len=strlen(s);
 84     for(int i=0;i<len;i++)
 85     if((s[i]>='a' && s[i]<='z')||(s[i]>='A' && s[i]<='Z'))
 86     {
 87         p=(s[i]>='a' && s[i]<='z')?s[i]-'a':s[i]-'A';
 88         while(j && !trie[j].next[p])
 89         {
 90             j=trie[j].pre;
 91         }
 92         j=trie[j].next[p];
 93         if(trie[j].tag)
 94         {
 95             pos[i+1]--;
 96             pos[i-trie[trie[j].tag].dep+1]++;
 97         }
 98     }
 99     else
100     {
101         j=0;
102         continue;
103     }
104     j=0;
105     for(int i=0;i<len;i++)
106     {
107         j+=pos[i];
108         if(j>0)
109             s[i]='*';
110     }
111     return ;
112 }
113 int T,n,m;
114 char s[N];
115 int main()
116 {
117     scanf("%d",&T);
118     while(T--)
119     {
120         init();
121         scanf("%d",&n);
122         gets(s);
123         for(int i=1;i<=n;i++)
124         {
125             gets(s);
126             add(0,s);
127         }
128         getfail();
129         gets(s);
130         acm(s);
131         printf("%s
",s);
132     }
133     return 0;
134 }
View Code

然后是按照论文里面bfs的构造法写的：

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<cstring>
  4 #include<queue>
  5 #define clr(x) memset(x,0,sizeof(x))
  6 #define clr_1(x) memset(x,-1,sizeof(x))
  7 #define INF 0x3f3f3f3f
  8 #define mod 1000000007
  9 #define LL long long
 10 #define next nexted
 11 using namespace std;
 12 const int N=1e6+100;
 13 const int type=26;
 14 struct node
 15 {
 16     int pre;
 17     int dep;
 18     int tag;
 19     int next[type];
 20 }trie[N];
 21 int tot;
 22 int pos[N];
 23 int newnode()
 24 {
 25    trie[++tot]=(node){};
 26     return tot;
 27 }
 28 void add(int root,char *s)
 29 {
 30     int len=strlen(s);
 31     int now=root;
 32     int p;
 33     for(int i=0;i<len;i++)
 34     {
 35         p=s[i]-'a';
 36         if(!trie[now].next[p])
 37             trie[now].next[p]=newnode();
 38         now=trie[now].next[p];
 39         trie[now].dep=i+1;
 40     }
 41     trie[now].tag=now;
 42 }
 43 void init()
 44 {
 45     tot=0;
 46     trie[0]=(node){};
 47     clr(pos);
 48     return ;
 49 }
 50 void build()
 51 {
 52     queue<int> que;
 53     int now,nowto;
 54     for(int i=0;i<type;i++)
 55         if(trie[0].next[i])
 56             que.push(trie[0].next[i]);
 57     while(!que.empty())
 58     {
 59         now=que.front();
 60         que.pop();
 61         for(int i=0;i<type;i++)
 62         {
 63             nowto=trie[now].next[i];
 64             if(nowto)
 65             {
 66                 que.push(nowto);
 67                 trie[nowto].pre=trie[trie[now].pre].next[i];
 68                 if(trie[trie[nowto].pre].tag && !trie[nowto].tag)
 69                     trie[nowto].tag=trie[trie[nowto].pre].tag;
 70             }
 71             else
 72                 trie[now].next[i]=trie[trie[now].pre].next[i];
 73         }
 74     }
 75     return ;
 76 }
 77 void acm(char *s)
 78 {
 79     int now=0,p,tmp;
 80     int len=strlen(s);
 81     for(int i=0;i<len;i++)
 82     if((s[i]>='a' && s[i]<='z')||(s[i]>='A' && s[i]<='Z'))
 83     {
 84         p=(s[i]>='a' && s[i]<='z')?s[i]-'a':s[i]-'A';
 85         now=trie[now].next[p];
 86         if(trie[now].tag)
 87         {
 88             pos[i+1]--;
 89             pos[i-trie[trie[now].tag].dep+1]++;
 90         }
 91     }
 92     else
 93     {
 94         now=0;
 95         continue;
 96     }
 97     now=0;
 98     for(int i=0;i<len;i++)
 99     {
100         now+=pos[i];
101         if(now>0)
102             s[i]='*';
103     }
104     return ;
105 }
106 int T,n,m;
107 char s[N];
108 int main()
109 {
110     scanf("%d",&T);
111     while(T--)
112     {
113         init();
114         scanf("%d",&n);
115         gets(s);
116         for(int i=1;i<=n;i++)
117         {
118             gets(s);
119             add(0,s);
120         }
121         build();
122         gets(s);
123         acm(s);
124         printf("%s
",s);
125     }
126     return 0;
127 }
View Code

tips: 虽然题目给的模式串总长不超过106然而实际不超过5*105,trie数组可以不开那么大，或者你改成孩子兄弟链法也是可行的。因为你一旦开那么大就会MLE。

然而你们看我代码为什么就不超呢。。我也是弄了好久才明白。。原来杭电他测内存占用的映射机制，只有当你使用过这个变量才会计算他是占用内存的。。所以你不写memset()或者对trie数组写指针引用的话，就不会超内存。

bzoj 2938

2938: [Poi2000]病毒

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1300  Solved: 647
[Submit][Status][Discuss]

Description

二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，是否存在一个无限长的安全的二进制代码。
示例：
例如如果{011, 11, 00000}为病毒代码段，那么一个可能的无限长安全代码就是010101…。如果{01, 11, 000000}为病毒代码段，那么就不存在一个无限长的安全代码。
任务：
请写一个程序：
l         读入病毒代码；
l         判断是否存在一个无限长的安全代码；
l         将结果输出

Input

 
第一行包括一个整数n，表示病毒代码段的数目。以下的n行每一行都包括一个非空的01字符串——就是一个病毒代码段。所有病毒代码段的总长度不超过30000。

Output

你应在在文本文件WIN.OUT的第一行输出一个单词：
l         TAK——假如存在这样的代码；
l         NIE——如果不存在。

Sample Input

3
01
11
00000

Sample Output

NIE
 

论文题。把Trie图构造出来以后dfs跑他的安全图看有没有环就行。有环说明能在这个环里一直跑，构造的字符串能无限长，无环则必定在某个位置到达词尾节点结束。

 1 #include<bits/stdc++.h>
 2 #define clr(x) memset(x,0,sizeof(x))
 3 #define clr_1(x) memset(x,-1,sizeof(x))
 4 #define INF 0x3f3f3f3f
 5 #define mod 1000000007
 6 #define LL long long
 7 #define next nexted
 8 using namespace std;
 9 const int N=3e4+10;
10 const int type=2;
11 char s[N];
12 int n,m,T,tot;
13 int vis[N];
14 struct node
15 {
16     int pre,tag,dep,next[2];
17 }trie[N];
18 void init()
19 {
20     tot=0;
21     clr(trie);
22     clr(vis);
23     return ;
24 }
25 int makenode()
26 {
27     return ++tot;
28 }
29 void add(int root,char *s)
30 {
31     int now=root,len=strlen(s),p;
32     for(int i=0;i<len;i++)
33     {
34         p=s[i]-'0';
35         if(!trie[now].next[p]) trie[now].next[p]=makenode();
36         now=trie[now].next[p];
37         trie[now].dep=i+1;
38     }
39     trie[now].tag=now;
40     return ;
41 }
42 void build()
43 {
44     queue<int> que;
45     for(int i=0;i<type;i++)
46         if(trie[0].next[i]) que.push(trie[0].next[i]);
47     int now,nowto;
48     while(!que.empty())
49     {
50         now=que.front();
51         que.pop();
52         for(int i=0;i<type;i++)
53         {
54             nowto=trie[now].next[i];
55             if(nowto)
56             {
57                 trie[nowto].pre=trie[trie[now].pre].next[i];
58                 que.push(nowto);
59                 if(trie[trie[nowto].pre].tag && !trie[nowto].tag)
60                     trie[nowto].tag=trie[trie[nowto].pre].tag;
61             }
62             else
63                 trie[now].next[i]=trie[trie[now].pre].next[i];
64         }
65     }
66     return ;
67 }
68 bool dfs(int now)
69 {
70     if(trie[now].tag || vis[now]==2) return 0;
71     if(vis[now]==1) return 1;
72     vis[now]=1;
73     bool inf=0;
74     for(int i=0;i<type;i++)
75         inf=(inf || dfs(trie[now].next[i]));
76     vis[now]=2;
77     return inf;
78 }
79 int main()
80 {
81     scanf("%d",&n);
82     init();
83     for(int i=1;i<=n;i++)
84     {
85         scanf("%s",s);
86         add(0,s);
87     }
88     build();
89     if(dfs(0))
90         printf("TAK
");
91     else
92         printf("NIE
");
93     return 0;
94 }
View Code

 bzoj 3670

3670: [Noi2014]动物园

Time Limit: 10 Sec  Memory Limit: 512 MB
Submit: 3403  Solved: 1849
[Submit][Status][Discuss]

Description

近日，园长发现动物园中好吃懒做的动物越来越多了。例如企鹅，只会卖萌向游客要吃的。为了整治动物园的不良风气，让动物们凭自己的真才实学向游客要吃的，园长决定开设算法班，让动物们学习算法。

某天，园长给动物们讲解KMP算法。

园长：“对于一个字符串S，它的长度为L。我们可以在O(L)的时间内，求出一个名为next的数组。有谁预习了next数组的含义吗？”

熊猫：“对于字符串S的前i个字符构成的子串，既是它的后缀又是它的前缀的字符串中（它本身除外），最长的长度记作next[i]。”

园长：“非常好！那你能举个例子吗？”

熊猫：“例S为abcababc，则next[5]=2。因为S的前5个字符为abcab，ab既是它的后缀又是它的前缀，并且找不到一个更长的字符串满足这个性质。同理，还可得出next[1] = next[2] = next[3] = 0，next[4] = next[6] = 1，next[7] = 2，next[8] = 3。”

园长表扬了认真预习的熊猫同学。随后，他详细讲解了如何在O(L)的时间内求出next数组。

下课前，园长提出了一个问题：“KMP算法只能求出next数组。我现在希望求出一个更强大num数组一一对于字符串S的前i个字符构成的子串，既是它的后缀同时又是它的前缀，并且该后缀与该前缀不重叠，将这种字符串的数量记作num[i]。例如S为aaaaa，则num[4] = 2。这是因为S的前4个字符为aaaa，其中a和aa都满足性质‘既是后缀又是前缀’，同时保证这个后缀与这个前缀不重叠。而aaa虽然满足性质‘既是后缀又是前缀’，但遗憾的是这个后缀与这个前缀重叠了，所以不能计算在内。同理，num[1] = 0,num[2] = num[3] = 1,num[5] = 2。”

最后，园长给出了奖励条件，第一个做对的同学奖励巧克力一盒。听了这句话，睡了一节课的企鹅立刻就醒过来了！但企鹅并不会做这道题，于是向参观动物园的你寻求帮助。你能否帮助企鹅写一个程序求出num数组呢？

特别地，为了避免大量的输出，你不需要输出num[i]分别是多少，你只需要输出对1,000,000,007取模的结果即可。

Input

第1行仅包含一个正整数n ，表示测试数据的组数。随后n行，每行描述一组测试数据。每组测试数据仅含有一个字符串S，S的定义详见题目描述。数据保证S 中仅含小写字母。输入文件中不会包含多余的空行，行末不会存在多余的空格。

Output

包含 n 行，每行描述一组测试数据的答案，答案的顺序应与输入数据的顺序保持一致。对于每组测试数据，仅需要输出一个整数，表示这组测试数据的答案对 1,000,000,007 取模的结果。输出文件中不应包含多余的空行。

Sample Input

3
aaaaa
ab
abcababc

Sample Output

36
1
32

HINT

n≤5,L≤1,000,000

 
这题是15年王鉴浩的论文题。对于本题我们对每个字符串算出next数组，并建立KMP自动机。然后dfs一遍KMP自动机，拿个数组存dfs经过点的编号。在节点u上，二分查找上述数组他所有小于等于u/2的祖先的个数，即为num[I]+1。
 1 #include<bits/stdc++.h>
 2 #define clr(x) memset(x,0,sizeof(x))
 3 #define clr_1(x) memset(x,-1,sizeof(x))
 4 #define mod 1000000007
 5 #define LL long long
 6 using namespace std;
 7 const int N=1e6+10;
 8 int next[N];
 9 struct edg
10 {
11     int next,to;
12 }edge[N];
13 int head[N],etot;
14 void init()
15 {
16     etot=0;
17     clr_1(head);
18     return ;
19 }
20 void addedge(int u,int v)
21 {
22     edge[++etot]=(edg){head[u],v};
23     head[u]=etot;
24     return ;
25 }
26 int que[N],ans[N];
27 char s[N];
28 int n,len,T,rans;
29 int getfail(int n,char *s)
30 {
31     int j=0,len=strlen(s);
32     next[0]=next[1]=0;
33     addedge(0,1);
34     for(int i=1;i<len;i++)
35     {
36         while(j && s[i]!=s[j]) j=next[j];
37         if(s[i]==s[j]) j++;
38         next[i+1]=j;
39         addedge(j,i+1);
40     }
41 }
42 void dfs(int u,int dep)
43 {
44     ans[u]=upper_bound(que+1,que+dep,u/2)-que;
45     ans[u]--;
46     que[dep]=u;
47     for(int i=head[u];i!=-1;i=edge[i].next)
48         dfs(edge[i].to,dep+1);
49     return ;
50 }
51 int main()
52 {
53     scanf("%d",&T);
54     while(T--)
55     {
56         init();
57         scanf("%s",s);
58         len=strlen(s);
59         getfail(n,s);
60         dfs(0,1);
61         rans=1;
62         for(int i=1;i<=len;i++)
63             rans=((LL)ans[i]*rans)%mod;
64         printf("%d
",rans);
65     }
66 
67 }
View Code

bzoj 3172

3172: [Tjoi2013]单词

Time Limit: 10 Sec  Memory Limit: 512 MB
Submit: 4761  Solved: 2333
[Submit][Status][Discuss]

Description

某人读论文，一篇论文是由许多单词组成。但他发现一个单词会在论文中出现很多次，现在想知道每个单词分别在论文中出现多少次。

Input

第一个一个整数N,表示有多少个单词，接下来N行每行一个单词。每个单词由小写字母组成，N<=200,单词长度不超过10^6

Output

输出N个整数，第i行的数字表示第i个单词在文章中出现了多少次。

Sample Input

3
a
aa
aaa

Sample Output

6
3
1

HINT

 

Source

此题最朴素想法就是建一个trie图然后在把原文章在trie图上跑一遍，把跑到的每个节点cnt都++。然后在dfs一遍trie树回溯时把节点的cnt加到他的后缀指针节点的cnt上。不过据说会TLE我就没尝试了，毕竟再跑一遍trie图实在是花时间。于是我们想这题能不能把大头的时间去掉。我的选择就是在建立trie图的时候也在原文章上跑，省去了再跑一遍的时间。做法就是建立的时候经过的点cnt++。然后你dfs整个trie树也好，建立一个fail树也好。都是要把所有节点dfs一遍的233。我选择fail树，毕竟是fail树练手题。也就是每个单词出现的次数即其词尾的子树cnt之和。

  1 #include<bits/stdc++.h>
  2 #define clr(x) memset(x,0,sizeof(x))
  3 #define clr_1(x) memset(x,-1,sizeof(x))
  4 #define mod 1000000007
  5 #define LL long long
  6 using namespace std;
  7 const int N=1e6+10;
  8 const int M=2e2+10;
  9 const int type=26;
 10 char s[N];
 11 int pt[M];
 12 struct node
 13 {
 14     int next[type],tag,sum,suf;
 15 }trie[N];
 16 int tot;
 17 int makenode()
 18 {
 19     ++tot;
 20     clr(&trie[tot]);
 21     return tot;
 22 }
 23 void add(char *s,int num)
 24 {
 25     int now=0,len=strlen(s),p;
 26     for(int i=0;i<len;i++)
 27     {
 28         p=s[i]-'a';
 29         if(!trie[now].next[p])
 30             trie[now].next[p]=makenode();
 31         now=trie[now].next[p];
 32         trie[now].sum++;
 33     }
 34     trie[now].tag=now;
 35     pt[num]=now;
 36     return ;
 37 }
 38 struct edg
 39 {
 40     int next,to;
 41 }edge[N];
 42 int head[N],etot;
 43 void addedge(int u,int v)
 44 {
 45     edge[++etot]=(edg){head[u],v};
 46     head[u]=etot;
 47     return ;
 48 }
 49 void init()
 50 {
 51     tot=etot=0;
 52     clr_1(head);
 53     return ;
 54 }
 55 void build()
 56 {
 57     int now,nowto;
 58     queue<int> que;
 59     for(int i=0;i<type;i++)
 60         if(trie[0].next[i])
 61         {
 62             que.push(trie[0].next[i]);
 63             addedge(0,trie[0].next[i]);
 64         }
 65     while(!que.empty())
 66     {
 67         now=que.front();
 68         que.pop();
 69         for(int i=0;i<type;i++)
 70         {
 71             nowto=trie[now].next[i];
 72             if(nowto)
 73             {
 74                 que.push(nowto);
 75                 trie[nowto].suf=trie[trie[now].suf].next[i];
 76                 addedge(trie[nowto].suf,nowto);
 77                 if(!trie[nowto].tag)
 78                         trie[nowto].tag=trie[trie[nowto].suf].tag;
 79             }
 80             else
 81                 trie[now].next[i]=trie[trie[now].suf].next[i];
 82         }
 83     }
 84     return ;
 85 }
 86 void dfs(int u)
 87 {
 88     for(int i=head[u];i!=-1;i=edge[i].next)
 89     {
 90         dfs(edge[i].to);
 91         trie[u].sum+=trie[edge[i].to].sum;
 92     }
 93     return ;
 94 }
 95 int n,m,T;
 96 int main()
 97 {
 98     init();
 99     scanf("%d",&n);
100     for(int i=1;i<=n;i++)
101     {
102         scanf("%s",s);
103         add(s,i);
104     }
105     build();
106     dfs(0);
107     for(int i=1;i<=n;i++)
108         printf("%d
",trie[pt[i]].sum);
109     return 0;
110 }
View Code

 bzoj 2434

2434: [Noi2011]阿狸的打字机

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 3996  Solved: 2194
[Submit][Status][Discuss]

Description

 阿狸喜欢收藏各种稀奇古怪的东西，最近他淘到一台老式的打字机。打字机上只有28个按键，分别印有26个小写英文字母和'B'、'P'两个字母。

经阿狸研究发现，这个打字机是这样工作的：

l 输入小写字母，打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。

l 按一下印有'B'的按键，打字机凹槽中最后一个字母会消失。

l 按一下印有'P'的按键，打字机会在纸上打印出凹槽中现有的所有字母并换行，但凹槽中的字母不会消失。

例如，阿狸输入aPaPBbP，纸上被打印的字符如下：

a

aa

ab

我们把纸上打印出来的字符串从1开始顺序编号，一直到n。打字机有一个非常有趣的功能，在打字机中暗藏一个带数字的小键盘，在小键盘上输入两个数(x,y)（其中1≤x,y≤n），打字机会显示第x个打印的字符串在第y个打印的字符串中出现了多少次。

阿狸发现了这个功能以后很兴奋，他想写个程序完成同样的功能，你能帮助他么？

Input

 输入的第一行包含一个字符串，按阿狸的输入顺序给出所有阿狸输入的字符。

第二行包含一个整数m，表示询问个数。

接下来m行描述所有由小键盘输入的询问。其中第i行包含两个整数x, y，表示第i个询问为(x, y)。

Output

 输出m行，其中第i行包含一个整数，表示第i个询问的答案。

Sample Input

aPaPBbP

3

1 2

1 3

2 3

Sample Output

2

1

0

HINT

 1<=N<=10^5


1<=M<=10^5

输入总长<=10^5

Source

Trie

 
AC自动机+Fail树+dfs时间戳+树状数组（离线处理）
 
首先建一颗Trie，根据输入字符串建树，遇到B返回父节点，P则是把当前节点作为第k个字符串词尾节点。其他字符则是按照正常建树过程建树。然后把它改造成Trie图并建立Fail树。
我们发觉第i个字符串在第j个字符串出现的次数，是第j个字符串的路径节点失配到第i个字符串的词尾节点p的个数（想想为什么？~）。即我们要统计fail树中p的子树中，第i个字符串路径节点的个数。
那我们把fail树的dfs时间戳求出来，我们的子树就对应了一个区间。
因此我们反过来，把第j个字符串经过的路径节点都+1，然后反过来求所有的i字符串对应的词尾节点的子树区间内的和。这个可以线段树也可以树状数组（当然树状数组啊写起来快一点）。
因此我们再跑一遍输入这个字符串，每跑过一个节点就把它对应的时间戳位置+1，返回就-1。跑到输出（P）第j个字符串的时候，把它所有对应的i都处理，求他们各自的p结点子树区间和，即为他们对应的答案。
  1 #include<bits/stdc++.h>
  2 #define clr(x) memset(x,0,sizeof(x))
  3 #define clr_1(x) memset(x,-1,sizeof(x))
  4 #define mod 1000000007
  5 #define LL long long
  6 #define time timed
  7 using namespace std;
  8 const int N=1e5+10;
  9 const int type=26;
 10 char s[N];
 11 int pt[N];
 12 struct node
 13 {
 14     int next[type],suf,fa;
 15 }trie[N];
 16 int tot,cnt,m;
 17 int makenode()
 18 {
 19     ++tot;
 20     clr(&trie[tot]);
 21     return tot;
 22 }
 23 struct edg
 24 {
 25     int next,to;
 26 }edge[N],ques[N];
 27 int head[N],qhead[N],qtot,etot;
 28 int ans[N];
 29 int u,v,time,fro[N],bac[N],len;
 30 int bits[N];
 31 void addedge(int u,int v)
 32 {
 33     edge[++etot].next=head[u];
 34     edge[etot].to=v;
 35     head[u]=etot;
 36     return;
 37 }
 38 void addques(int u,int v)
 39 {
 40     ques[++qtot].next=qhead[u];
 41     ques[qtot].to=v;
 42     qhead[u]=qtot;
 43     return;
 44 }
 45 void init()
 46 {
 47     cnt=tot=0;
 48     etot=qtot=0;
 49     time=0;
 50     clr_1(head);
 51     clr_1(qhead);
 52     clr(bits);
 53 }
 54 void create(char *s)
 55 {
 56     int now=0,len=strlen(s),p;
 57     for(int i=0;i<len;i++)
 58     {
 59         if(s[i]=='B') now=trie[now].fa;
 60         else if(s[i]=='P') pt[++cnt]=now;
 61         else
 62         {
 63             p=s[i]-'a';
 64             if(!trie[now].next[p])
 65             {
 66                 trie[now].next[p]=makenode();
 67                 trie[trie[now].next[p]].fa=now;
 68             }
 69             now=trie[now].next[p];
 70         }
 71     }
 72 }
 73 void build()
 74 {
 75     queue<int> que;
 76     int now,nowto;
 77     for(int i=0;i<type;i++)
 78     if(trie[0].next[i])
 79     {
 80         addedge(0,trie[0].next[i]);
 81         que.push(trie[0].next[i]);
 82     }
 83     while(!que.empty())
 84     {
 85         now=que.front();
 86         que.pop();
 87         for(int i=0;i<type;i++)
 88         {
 89             nowto=trie[now].next[i];
 90             if(nowto)
 91             {
 92                 que.push(nowto);
 93                 trie[nowto].suf=trie[trie[now].suf].next[i];
 94                 addedge(trie[nowto].suf,nowto);
 95             }
 96             else
 97                 trie[now].next[i]=trie[trie[now].suf].next[i];
 98         }
 99     }
100     return ;
101 }
102 void dfs(int u)
103 {
104     fro[u]=++time;
105     for(int i=head[u];i!=-1;i=edge[i].next) dfs(edge[i].to);
106     bac[u]=time;
107     return ;
108 }
109 void add(int x,int val)
110 {
111     while(x<=time)
112     {
113         bits[x]+=val;
114         x+=x&-x;
115     }
116     return ;
117 }
118 int getsum(int x)
119 {
120     int ans=0;
121     while(x)
122     {
123         ans+=bits[x];
124         x-=x&-x;
125     }
126     return ans;
127 }
128 void getans(char *s)
129 {
130     int now=0,len=strlen(s),p;
131     int ct=0;
132     for(int i=0;i<len;i++)
133     {
134         if(s[i]=='B')
135         {
136             add(fro[now],-1);
137             now=trie[now].fa;
138         }
139         else if(s[i]=='P')
140         {
141             ct++;
142             for(int i=qhead[ct];i!=-1;i=ques[i].next)
143             {
144                 p=ques[i].to;
145                 ans[i]=getsum(bac[pt[p]])-getsum(fro[pt[p]]-1);
146             }
147         }
148         else
149         {
150             p=s[i]-'a';
151             now=trie[now].next[p];
152             add(fro[now],1);
153         }
154     }
155     return ;
156 }
157 int main()
158 {
159     scanf("%s",s);
160     init();
161     create(s);
162     build();
163     scanf("%d",&m);
164     for(int i=1;i<=m;i++)
165     {
166         scanf("%d%d",&u,&v);
167         addques(v,u);
168     }
169     dfs(0);
170     getans(s);
171     for(int i=1;i<=m;i++)
172         printf("%d
",ans[i]);
173     return 0;
174 }
View Code
 bzoj 3881

3881: [Coci2015]Divljak

Time Limit: 20 Sec  Memory Limit: 512 MB
Submit: 1041  Solved: 340
[Submit][Status][Discuss]

Description

Alice有n个字符串S_1,S_2...S_n，Bob有一个字符串集合T，一开始集合是空的。
接下来会发生q个操作，操作有两种形式：
“1 P”，Bob往自己的集合里添加了一个字符串P。
“2 x”，Alice询问Bob，集合T中有多少个字符串包含串S_x。（我们称串A包含串B，当且仅当B是A的子串）
Bob遇到了困难，需要你的帮助。
 
 

Input

第1行，一个数n；
接下来n行，每行一个字符串表示S_i；
下一行，一个数q；
接下来q行，每行一个操作，格式见题目描述。

Output

对于每一个Alice的询问，帮Bob输出答案。

Sample Input

3
a
bc
abc
5
1 abca
2 1
1 bca
2 2
2 3

Sample Output

1
2
1

HINT

【数据范围】

1 <= n,q <= 100000；

Alice和Bob拥有的字符串长度之和各自都不会超过 2000000；

字符串都由小写英文字母组成。
AC自动机+Fail树+dfs时间戳+虚树（树链的并?）+树状数组
跟上一题差不多，不过我们这次要做的不是包含多少个子串，而是被多少串包含。那么你先把所有alice的字符串建一个Trie图，建立fail树。然后bob加入字符串的时候就相当于在这个trie图上跑，经过的路径点染上相同的颜色。alice询问的时候就相当于查询这个字符串尾节点的子树有多少不同的颜色。
然后难就难在这个不同颜色。你对于所有路径点+根节点点（root）建立虚树。然后每个点给他+1，他的父亲节点-1。这样就能得出结果了。
抄错了虚树板子卡了我好久，其实就是抄一个正确的虚树板子就过了。
  1 #include<cstdio>
  2 #include<iostream>
  3 #include<cstring>
  4 #include<stack>
  5 #include<queue>
  6 #include<algorithm>
  7 #define clr(x) memset(x,0,sizeof(x))
  8 #define clr_1(x) memset(x,-1,sizeof(x))
  9 #define mod 1000000007
 10 #define LL long long
 11 using namespace std;
 12 const int N=2e6+10;
 13 const int M=1e5+10;
 14 const int type=26;
 15 struct node{
 16     int next[type],suf;
 17 }trie[N];
 18 int tcnt;
 19 char s[N];
 20 int pt[M];
 21 queue<int> que;
 22 stack<int> sta;
 23 struct edg
 24 {
 25     int next,to;
 26 }edge[N];
 27 int head[N],ecnt;
 28 int fa[N][23],bit[23];
 29 int clk,fro[N],bac[N],dep[N];
 30 int tot,ppt[N],vfa[N];
 31 int bits[N];
 32 void add(int x,int val)
 33 {
 34     while(x<=clk)
 35     {
 36         bits[x]+=val;
 37         x+=x&-x;
 38     }
 39     return ;
 40 }
 41 int getsum(int x)
 42 {
 43     int ans=0;
 44     while(x)
 45     {
 46         ans+=bits[x];
 47         x-=x&-x;
 48     }
 49     return ans;
 50 }
 51 inline int sum(int l,int r)
 52 {
 53     return getsum(r)-getsum(l-1);
 54 }
 55 void init()
 56 {
 57     tcnt=0;
 58     ecnt=0;
 59     clr_1(head);
 60     bit[0]=1;
 61     for(int i=1;i<23;i++)
 62         bit[i]=bit[i-1]<<1;
 63     clk=0;
 64     return ;
 65 }
 66 int makenode()
 67 {
 68     ++tcnt;
 69     memset(&trie[tcnt],0,sizeof(trie[tcnt]));
 70     return tcnt;
 71 }
 72 void addedge(int u,int v)
 73 {
 74     edge[++ecnt].next=head[u];
 75     edge[ecnt].to=v;
 76     head[u]=ecnt;
 77     return;
 78 }
 79 int insert(char *s)
 80 {
 81     int now=0,p;
 82     for(int i=0;s[i];i++)
 83     {
 84         p=s[i]-'a';
 85         if(!trie[now].next[p])
 86             trie[now].next[p]=makenode();
 87         now=trie[now].next[p];
 88     }
 89     return now;
 90 }
 91 void build()
 92 {
 93     int now=0,nowto;
 94     for(int i=0;i<type;i++)
 95         if(trie[now].next[i])
 96             que.push(trie[now].next[i]);
 97     while(!que.empty())
 98     {
 99         now=que.front();
100         que.pop();
101         for(int i=0;i<type;i++)
102         {
103             nowto=trie[now].next[i];
104             if(!nowto)
105                 trie[now].next[i]=trie[trie[now].suf].next[i];
106             else
107                 que.push(nowto),trie[nowto].suf=trie[trie[now].suf].next[i];
108         }
109     }
110     for(int i=1;i<=tcnt;i++)
111         addedge(trie[i].suf,i);
112     return ;
113 }
114 void dfs(int u,int deep,int f)
115 {
116     dep[u]=deep;
117     fa[u][0]=f;
118     fro[u]=++clk;
119     for(int i=1;bit[i]<=deep;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
120     for(int i=head[u];~i;i=edge[i].next)
121         dfs(edge[i].to,deep+1,u);
122     bac[u]=clk;
123 }
124 bool cmp(int a,int b)
125 {
126     return fro[a]<fro[b];
127 }
128 int lca(int u,int v)
129 {
130     if(dep[u]<dep[v]) swap(u,v);
131     int tmp=dep[u]-dep[v];
132     for(int i=0;bit[i]<=tmp;i++)
133         if(tmp&bit[i]) u=fa[u][i];
134     int i=22;
135     while(bit[i]>dep[u]) i--;
136     for(;i>=0;i--)
137         if(fa[u][i]!=fa[v][i]) {u=fa[u][i]; v=fa[v][i];}
138     return (u==v)?(u):(fa[u][0]);
139 }
140 void ins(char *s)
141 {
142     int p,now=0,x;
143     tot=0;
144     ppt[++tot]=0;
145     for(int i=0;s[i];i++)
146     {
147         p=s[i]-'a';
148         now=trie[now].next[p];
149         ppt[++tot]=now;
150     }
151     sort(ppt+1,ppt+tot+1,cmp);
152     tot=unique(ppt+1,ppt+tot+1)-ppt-1;
153     for(int i=1,nowtot=tot;i<=nowtot;i++)
154     {
155         if(sta.empty()) {sta.push(ppt[i]);vfa[ppt[i]]=-1;continue;}
156         p=lca(ppt[i],sta.top());
157         while(!sta.empty() && dep[sta.top()]>dep[p])
158         {
159             x=sta.top();
160             sta.pop();
161             if((!sta.empty()&& dep[sta.top()]<=dep[p]) || sta.empty())
162                 vfa[x]=p;
163         }
164         if(!sta.empty() && sta.top()!=p)
165         {
166             vfa[p]=sta.top();
167             sta.push(p);
168             ppt[++tot]=p;
169         }
170         else if(sta.empty())
171         {
172             vfa[p]=-1;
173             sta.push(p);
174             ppt[++tot]=p;
175         }
176         vfa[ppt[i]]=p; sta.push(ppt[i]);
177     }
178     for(int i=1;i<=tot;i++)
179     {
180         if(vfa[ppt[i]]==-1) continue;
181         add(fro[ppt[i]],1);
182         add(fro[vfa[ppt[i]]],-1);
183     }
184     while(!sta.empty())
185         sta.pop();
186     return ;
187 }
188 int main()
189 {
190     int n,m,op,ques;
191     init();
192     scanf("%d",&n);
193     for(int i=1;i<=n;i++)
194     {
195         scanf("%s",s);
196         pt[i]=insert(s);
197     }
198     build();
199     dfs(0,0,0);
200     scanf("%d",&m);
201     for(int i=1;i<=m;i++)
202     {
203         scanf("%d",&op);
204         if(op==1)
205         {
206             scanf("%s",s);
207             ins(s);
208         }
209         else
210         {
211             scanf("%d",&ques);
212             printf("%d
",sum(fro[pt[ques]],bac[pt[ques]]));
213         }
214     }
215     return 0;
216 }
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/wujiechao/p/8675612.html