十八章做题记录 · Zhl2010 第二博客

KMP

模板

KMP 的思想主要是有一个 kmp 数组，然后记录匹配失败后，需要移动到哪里。

每一个位置只需要进行一次比较。

然后代码比较直观。

代码

C++

#include<bits/stdc++.h>
#define int long long
using namespace std;
char s[1000010],t[1000010];
int kmp[1000010];


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

扩展 KMP

P5410 【模板】扩展 KMP / exKMP（Z 函数）。

这篇 TJ 讲的清楚，C 过来。

结论： 对于 $i>0$ ，对任意 $0\le l<i$ 都可以递推得：

$\forall 0\le x<\min(z(i-l),l+z(l)-i),s[(i)+(x)]=s[(0)+(x)]$

证明：

主要思想是将这个位置转换成前面的一个位置加上一个位移，然后这个位置的 $z$ 函数我们是知道的，只需要移动到 $0$ 就可以转换成下一个函数了。

\begin{aligned} &s[(i)+(x)]\\ =&s[(l)+(i+x-l)]\\ =&s[(0)+(i+x-l)]\color{red}{(x\le l+z(l)-i)}\\ =&s[(i-l)+(x)]\\ =&s[(0)+(x)]\color{red}{(x\le z(i-l))}\\ \end{aligned}

初始化 $z(i)=\min(z(i-l),l+z(l)-i)$ ，然后暴力判断字符相等增加 $z(i)$ 。

这里 $l$ 选满足 $j+z(j)(0\le j<i)$ 最大的 $j$ ，这样每个字符只会被暴力判断一次（如果最小值是 $z(i-l)$ 就会第一次就失配），所以时间复杂度可以做到 $\Theta(n)$ 。

对于题目中的问题其实把 $b$ 和 $a$ 接起来做个 $z$ 就可以了。

最小表示法

P13270 【模板】最小表示法。

先断环成链放两个。

先放 $i$ 和 $j$ ，表示最小的和当前的（下标小的设置为最小的）。

然后如果 $i$ 是最小的，然后现在有来了一个 $j$ ，先把能匹配的 $k$ 位匹配。

如果 $i$ 更小， $j$ 就变成 $j+k+1$ ，因为这中间的一定比 $i$ 到 $i+k+1$ 中间的某一个大（他们匹配了一些位置了）。

如果 $j$ 更小， $i$ 变成 $i+k+1$ 。

复杂度易证。

代码

C++

#include<bits/stdc++.h>
using namespace std;
int n;
char s[20000010];



signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	cin>>(s+1);
	for(int i=1;i<=n;i++){
		s[i+n]=s[i];
	}
	int i=1,j=2;
	for(;i<=n&&j<=n;){
		int k=0;
		while(k<=n&&s[i+k]==s[j+k])k++;
		if(s[i+k]>s[j+k]) i+=k+1;
		else j+=k+1;
		if(i==j)j++;//不要漏 
	}
	int ans=min(i,j);
	for(int i=ans;i<=ans+n-1;i++)cout<<s[i];
	cout<<endl;
	
	return 0;
}