[COGS 2248] 情书 AC自动机模板

【题目描述】#

John平静的生活最近有了波澜：他已经连续n天受到陌生人的情书了。小小的心中充满了憧憬，但是某些人觉得有乐子可以找，决定伪造情书。John总结出了那个陌生人写信的习惯，也就是某些关键的字符串。如果一封信中这若干个关键字符串都出现，他就认为这是那个陌生人写的，否则就是他同学的恶作剧。注意，John可能收到多封情书。

【输入格式】#

第一行一个整数n，表示关键字符串的个数，n<=100。
接下来n行，每行为一个长度不超过100的字符串。最后是若干段文本，每段文本以 $ 结尾。
由于写情书的人太疯狂，每封情书最长可以达到1350000个字符，但情书的个数不超过10。

【输出格式】#

对于每一段文本对应一行输出。
‘Yes’表示是陌生人的来信，‘No’表示不是。
请注意大小写。

【样例输入】#

1
3
2
i
3
love
4
wzk
5
ilovewzk$
6
lovewzk$

【样例输出】#

1
Yes
2
No

题解#

AC自动机板子
感谢TS_Hugh , LadyLex

1
#include<iostream>
2
#include<cstdio>
3
#include<cstring>
4
#include<vector>
5
using namespace std;
6
char text[1350005];
7
int n;
8
struct Trie{
9
    vector<int> Q;
10
    Trie *ch[26],*fail;
11
    Trie(){
12
        Q.clear();memset(ch,0,sizeof(ch));fail=NULL;
13
    }
14
    void* operator new(size_t size);
15
}*root,*C,*num,*Q[100005];
16
void* Trie::operator new(size_t size){
17
    if(C==num){
18
        C=new Trie[1<<15];
19
        num=C+(1<<15);
20
    }
21
    return C++;
22
}
23
void insert(char *s,int x){
24
    int len=strlen(s);
25
    Trie *now=root;
26
    for(int i=0;i<len;i++){
27
        if(now->ch[s[i]-'a']==NULL)now->ch[s[i]-'a']=new Trie();
28
        now=now->ch[s[i]-'a'];
29
    }
30
    now->Q.push_back(x);
31
}
32
void build()
33
{
34
    root->fail=NULL;
35
    Q[0]=root;
36
    for(int i=0,j=0;i<=j;i++){
37
        for(int l=0;l<26;l++){
38
            if(Q[i]->ch[l]){
39
                Trie *now=Q[i]->fail;
40
                while(now&&!now->ch[l])now=now->fail;
41
                Q[i]->ch[l]->fail=now?now->ch[l]:root;
42
                Q[++j]=Q[i]->ch[l];
43
            }
44
        }
45
    }
46
}
47
bool read(){
48
    char c;
49
    int head=0;
50
    if(cin>>c){
51
        while(c!='$'){
52
            if(c=='\n'||c==' '){c=getchar();continue;}
53
            text[head++]=c;c=getchar();
54
        }
55
        text[head++]='$';
56
        return 1;
57
    }
58
    return 0;
59
}
60
bool via[105];
61
void work(){
62
    memset(via,0,sizeof(via));
63
    Trie *now=root;
64
    for(int i=0;text[i]!='$';i++){
65
        while(now&&!now->ch[text[i]-'a'])now=now->fail;
66
        now=now?now->ch[text[i]-'a']:root;
67
        for(Trie *i=now;i;i=i->fail){
68
            if(!i->Q.empty()){
69
                int l=i->Q.size();
70
                for(int j=0;j<l;j++)via[i->Q[j]]=1;
71
            }
72
        }
73
    }
74
    int ans=0;
75
    for(int i=1;i<=n;i++)if(via[i])ans++;
76
    if(ans==n)puts("Yes");
77
    else puts("No");
78
}
79
int main()
80
{
81
    freopen("lettera.in","r",stdin);
82
    freopen("lettera.out","w",stdout);
83
    root=new Trie();
84
    char s[1000];
85
    scanf("%d",&n);
86
    for(int i=1;i<=n;i++){
87
        scanf("%s",s);
88
        insert(s,i);
89
    }
90
    build();
91
    while(read()) work();
92
}