文本串

T

ext
模式串

P

attern

字符串匹配 KMP

在

T

中找到所有

P

的出现位置。

KMP 算法

使用双指针法预处理出

P

的

nxt[]

。（即

P

匹配

P

）
再使用相似的方法进行匹配。（即

P

匹配

T

）

代码

CPP

12345678910111213141516171819	cin>>(t+1)>>(s+1);
	n=strlen(s+1);
	m=strlen(t+1);
	
	nxt[1]=0;
	for(int i=2,j=0;i<=n;i++){
		while(j && s[i]!=s[j+1])j=nxt[j];
		if(s[i]==s[j+1])j++;
		nxt[i]=j;
	}
	
	for(int i=1,j=0;i<=m;i++){
		while(j && t[i]!=s[j+1])j=nxt[j];
		if(t[i]==s[j+1])j++;
		if(j==n){
			cout<<i-j+1<<"\n";
			j=nxt[j];
		}
	}

时间复杂度可以证明为

O(\mid P\mid+\mid T\mid)

。
第一个 for 是求

P

的

nxt[]

数组，时间组复杂度

O(\mid P\mid)

。
第一个 for 是进行匹配，时间组复杂度

O(\mid T\mid)

。
证明方式都是因为

j

减少次数不能超过其增加次数。

字典树 Trie

人类查字典本质就是二分策略

约定字符集

\Sigma

。

字典：一个排序所有的单词，一般来说需要二分。
字典树：构造树形结构分叉，快速查找单词。

基本要素

字典树上节点代表某个单词的前缀（根链即为字符串）。
边上存的是字母。

插入

如果有路就走路，如果没路就开路。

高效

将多件事情融合起来（公共前缀）。

归零边

字典树不仅仅是普通树。
归零边 代表

nxt[u][c]=0

的空边，也就是还没开的边。
这是代码层面上额边。
去除规定边后才是树。

节点数：

O(\sum{\mid P\mid})

空间复杂度：

O(\mid \Sigma\mid \times \sum{\mid P\mid})

AC 自动机

Aho-Corasic automaton

自动机

自动机是自动做事的机器。
自动：只看局部，不看全局。
自动机：一个人在图中自动走路。

Trie + KMP

对每个节点添加

fail[]

指针。

fail

AC 自动机有两棵树。
一颗是

trie

，一个是

fail

，因此后面可以在两树间切换来解决问题。

fail

树总是向上的，因此我们一般使用 BFS 来计算。

预处理 fail

对于父亲到儿子

u \to v

，边是

c

。

fail[v]=nxt[fail[u]][c]

但是对于归零边我们要做优化，对应 KMP 中第二指针不停跳。

nxt[u][c]=nxt[fail[u]][c]

这个优化被称为归零边重定向。
预处理复杂度：

O(\mid \Sigma\mid \times \sum{\mid P\mid})

。

匹配

直接走，但是每次要找后缀。

确定有限状态自动机。

字符串基础

文章操作