【学习笔记】字符串

1.KMP

【模板】KMP

朴素的比对是如下的：

for(int i=0;i<a.size()-b.size();i++){
	for(int j=0;j<b.size();j++){
   		if(a[i+j]!=b[j])break;
		if(j==b.size()-1)cout<<i<<' ';
	}
}

设 A 串长度 \(n\)，B 串长度 \(m\)，显然这么做是 \(O(nm)\) 的。

很容易想到一个错误优化：如果失败直接从当前位置找起。

反例很容易给出：在 \(\text{ababac}\) 中找 \(\text{abac}\)。我们在找到第一个 \(\text{abab}\) 后发现失配会直接从下一个 \(\text{a}\) 开始，从而错过正确答案。

分析一下错因：在匹配失败后可能在当前串有作为下一个串的开头的子串而我们舍去了。

如果我们知道在找到 \(\text{abcab}\) 时 \(\text{ab}\) 可能作为新的开头从而从 \(\text{ab}\) 开始，就能在保证正确性的情况下大幅加快效率。

2.Manacher 马拉车

3.AC 自动机

4.PAM

咕咕。

5.SA

咕咕咕。

6.SAM

咕咕咕咕。