Prefix Function Queries
题目传送门
题意
有一个长度为 $n(1 \leq n \leq 10^6)$ 的字符串 $s$ ，有 $q(1 \leq q \leq 10^5)$ 次询问。
每次询问给出一个非空字符串 $t(1 \leq |t| \leq 10)$ ，如果把 $t$ 拼接到 $s$ 的后面，求长度为 $n+1,n+2, \dots ,n+|t|$ 的前缀的最长相同前缀后缀。（即求 $KMP$ 中的 $pmt$ 数组的 $pmt[n+1],pmt[n+2], \dots ,pmt[n+|t|]$ ）。
思路
我刚开始感觉这就是个 $KMP$ 的裸题，但是在我交了上去并发现 $T$ 了的时候，感觉又不像是 $KMP$ 。
然后，在今天题解出来之后，我看了一下，发现了一个叫前缀函数自动机的东西，这个东西和 $AC自动机$ 极其类似，都有一个叫失配指针的东西，然后这东西又有点像 $Trie 树$ ，有着相似的转移。
代码
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
| #include<bits/stdc++.h>
#define Inf 0x3f3f3f3f
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
const int MAXX=1000050;
int n,q;
char s[MAXX];
int fail[MAXX],ch[MAXX][26];
inline void solve(){
scanf("%s%d",s+1,&q);
n=strlen(s+1);
ch[0][s[1]-'a']=1;
for(int i=2;i<=n;++i){
for(int j=0;j<26;++j){
if(s[i]-'a'==j){
ch[i-1][j]=i;
fail[i]=ch[fail[i-1]][j];
}
else
ch[i-1][j]=ch[fail[i-1]][j];
}
}
while(q--){
getchar();scanf("%s",s+n+1);
int nn=strlen(s+n+1)+n;
for(int i=n+1;i<=nn;++i){
for(int j=0;j<26;++j){
if(s[i]-'a'==j){
ch[i-1][j]=i;
fail[i]=ch[fail[i-1]][j];
}
else
ch[i-1][j]=ch[fail[i-1]][j];
}
}
for(int i=n+1;i<=nn;++i)
printf("%d%c",fail[i]," \n"[i==nn]);
}
}
signed main(){
solve();
return 0;
}
|
总结
感觉这个东西在只需要求 $pmt$ 数组的时候，可以作为 $KMP$ 的替代品。
