定义

前缀

对于字符串 $S$，从串首开始到某个位置 $i$ 结束的子串，叫做 $S$ 的一个前缀，除 $S$ 本身外的所有前缀叫做 $S$ 的真前缀。

后缀

与前缀类似，从某位置 $i$ 到串尾的一个字串叫做后缀，同样有真后缀。

字典树/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
int id(char c){
	if(c>='A'&&c<='Z')
		return c-'A';
	else if(c>='a'&&c<='z')
		return c-'a'+26;
	else
		return c-'0'+52;
}
struct Trie{
	int nxt[N][65],tot,cnt[N];
	bool end[N];
	void init(){
		for(int i=0;i<=tot;i++)
			for(int j=0;j<=64;j++)
				nxt[i][j]=0;
		for(int i=0;i<=tot;i++)
			cnt[i]=0,end[i]=0;
		tot=0;
		return;
	}
	void insert(char s[]){
		int p=0,len=strlen(s);
		for(int i=0;i<len;i++){
			int c=id(s[i]);
			if(!nxt[p][c])
				nxt[p][c]=++tot;
			p=nxt[p][c];
			cnt[p]++;
		}
		end[p]=1;
		return;
	}
	int find(char s[]){
		int p=0,len=strlen(s);
		for(int i=0;i<len;i++){
			int c=id(s[i]);
			if(!nxt[p][c])
				return 0;
			p=nxt[p][c];
		}
		return cnt[p];
	}
};

应用

字符串查找，前缀统计等。
一些关于后缀的操作可以反转字符串变为前缀操作。

KMP 算法

进行 KMP 算法的过程其实就是在求一个叫做最长公共前后缀的东西。
定义一个字符串 $S$ 的 border 为 $S$ 的一个非 $S$ 本身的子串 $T$，满足 $T$ 既是 $S$ 的前缀，又是 $S$ 的后缀。求解最大 border。

1
2
3
4
5
6
7
8
9
int j=0;
nxt[1]=0;//nxt[i]表示字串S[1...i]的最大border的长度
for(int i=2;i<=len;i++){
	while(j&&s[j+1]!=s[i])
		j=nxt[j];
	if(s[j+1]==s[i])
		j++;
	nxt[i]=j;
}

应用

查找 $S_2$ 串在 $S_1$ 串的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int j=0;
for(int i=2;i<=len2;i++){
	while(j&&s2[j+1]!=s2[i])
		j=nxt[j];
	if(s2[j+1]==s2[i])
		j++;
	nxt[i]=j;
}
j=0;
for(int i=1;i<=len1;i++){
	while(j&&s2[j+1]!=s1[i])
		j=nxt[j];
	if(s2[j+1]==s1[i])
		j++;
	if(j==len2){
		printf("%d\n",i-j+1);
		j=nxt[j];
	}
}

另一种方法是，构建一个新字符串 $S=S_2+a+S_1$，进行一次 KMP，若某点 $nxt$ 值等于 $S_2$ 的长度则找到了一个解。$a$ 为字符集以外的任意字符，如 #。