【AC自动机】玄武密码

【题目链接】

【题意】

对于每一段文字，其前缀在母串上的最大匹配长度是多少呢

【参考别人的题解】

https://www.luogu.org/problemnew/solution/P5231

我们只需要先建立所有密码的trie树
再以母串为主串跑一个AC自动机
不过其中还是有一些需要改动的地方
原本字典树中用来记录某个节点是不是字符串结尾的数组不需要，直接删去
我们需要另一个数组来标记哪些点被匹配
跑完ac自动机后从trie树上找最后一个匹配的点即可
优化：由于nxt数组是递归到0的所以只要有一个点被标记过，那么这个点到0的所有点都已经被遍历过直接退出即可

【自己理解】

其实这个题目就是套路。

1、建模式串的AC自动机。

2、利用文本串跑一遍AC自动机，把对应的位置标记上。

3、再跑一遍模式串，去最长的位置就是答案了。

【代码】

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int M = 2e7 + 5 ;
 6 const int N = 2e5+5 ;
 7 char T[M];
 8 char P[N][205];
 9 int Trie[M][4],Match[M],fail[M],Cnt[M];
10 int Q[M],Head,Tail;
11 int n,m,idx=1;
12 
13 int calc( char x ){
14     if( x == 'N' ) return 0;
15     else if( x=='E' ) return 1;
16     else if( x=='S' ) return 2;
17     else return 3;
18 }
19 void Insert(char s[],int Id){
20     int p = 1;
21     for(int i=0;s[i];i++){
22         int t = calc(s[i]);
23         if( !Trie[p][t] )
24             Trie[p][t] = ++idx ;
25         p = Trie[p][t];
26     }
27     Match[Id] = p ;
28 }
29 void Build(){
30     Head = 1 , Tail = 0 ;
31     for(int i=0;i<4;i++) Trie[0][i] = 1;
32 
33     Q[++Tail] = 1 ;
34     while( Head <= Tail ){
35         int u = Q[Head++] ;
36         for(int i=0;i<4;i++){
37             int To = Trie[u][i];
38             if( To ){
39                 fail[To] = Trie[fail[u]][i];
40                 Q[ ++Tail ] = To ;
41             }else{
42                 Trie[u][i] = Trie[fail[u]][i];
43             }
44         }
45     }
46 }
47 void Query(char T[]){
48 
49     int p = 1 ;
50     for(int i=0;T[i];i++){
51         p = Trie[p][calc(T[i])];
52         for(int j=p;j;j=fail[j]){
53             if( Cnt[j] ) break;
54             Cnt[j] = 1 ;
55         }
56     }
57 
58     for(int i=1;i<=m;i++){
59         int res = 0 , p = 1 ;
60         for(int j=0;P[i][j];j++){
61             p = Trie[p][calc(P[i][j])];
62             if( Cnt[p] ) res = j + 1 ;
63         }
64         printf("%d
",res);
65     }
66 }
67 int main()
68 {
69     scanf("%d%d",&n,&m);
70     scanf("%s",T);
71     for(int i=1;i<=m;i++){
72         scanf("%s",P[i]);
73         Insert( P[i] , i );
74     }
75     Build();
76     Query(T);
77     return 0 ;
78 }

玄武密码