Codeforces 432D Prefixes and Suffixes (KMP、后缀数组)

题目链接: https://codeforces.com/contest/432/problem/D

题解:

做法一: KMP

显然next树上\(n\)的所有祖先都是答案，出现次数为next树子树大小。

做法二: 后缀数组/Z-box

按照height分组，二分查找即可。

这种题经常KMP和Z-box都能做。

另外哪位神犇教我一下扩展KMP和Z-box有啥区别。

代码

KMP:

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<vector>

#include<utility>

using namespace std;

const int N = 1e5;

char a[N+3];

int nxt[N+3];

int sz[N+3];

vector<pair<int,int> > ans;

int n;

void KMP()

{

	nxt[0] = nxt[1] = 0;

	for(int i=2; i<=n; i++)

	{

		nxt[i] = nxt[i-1];

		while(nxt[i] && a[nxt[i]+1]!=a[i])

		{

			nxt[i] = nxt[nxt[i]];

		}

		if(a[nxt[i]+1]==a[i]) nxt[i]++;

	}

}

int main()

{

	scanf("%s",a+1); n = strlen(a+1);

	for(int i=1; i<n+1-i; i++) swap(a[i],a[n+1-i]);

	KMP();

	for(int i=1; i<=n; i++) sz[i] = 1;

	for(int i=n; i>=1; i--) sz[nxt[i]] += sz[i];

	for(int i=n; i>0; i=nxt[i])

	{

		ans.push_back(make_pair(i,sz[i]));

	}

	printf("%d\n",ans.size());

	for(int i=ans.size()-1; i>=0; i--) printf("%d %d\n",ans[i].first,ans[i].second);

	return 0;

}

巴特西

Codeforces 432D Prefixes and Suffixes (KMP、后缀数组)

代码

最新文章

热门文章