Codeforces 126B. Password（KMP，DP）

Codeforces 126B. Password

题意：一个字符串，找出最长的子串t，它既是前缀又是后缀，还出现在中间。输出t，不存在则输出Just a legend。

思路：利用KMP算法处理出next数组，由next数组的意义可以知道i为尾的最长相同前缀后缀。则ne[n-1]，ne[ne[n-1]],ne[ne[ne[n-1]]]......均为可能的解，且长度递减，为了高效的逐一验证，则需要预处理出整个字符串有多少个与该前缀相同的子串。用到DP思想，cnt[next[i]]+=cnt[i],倒着更新一遍，即可处理出上述信息。那么cnt大等于3的前缀，均为可行解

代码：

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<string>

#define dd(x) cout<<#x<<" = "<<x<<" "

#define de(x) cout<<#x<<" = "<<x<<"\n"

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

using namespace std;

typedef long long ll;

typedef long double ld;

const int maxn=1e6+10,mod=1e9+7,INF=0x3f3f3f3f;

char s[maxn];

int ne[maxn],cnt[maxn];

void init()

{

	ne[0]=-1;

	for (int i=1;s[i];++i)

	{

		int j=ne[i-1];

		while (s[j+1]!=s[i]&&j>=0)

			j=ne[j];

		if (s[j+1]==s[i])

			ne[i]=j+1;

		else

			ne[i]=-1;

	}

}

int main()

{

	scanf("%s",s);

	init();

	int n=strlen(s);

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

		cnt[i]=1;

	for (int i=n-1;i;--i)

		cnt[ne[i]]+=cnt[i];

	for (int i=ne[n-1];i!=-1;i=ne[i])

	{

		if (cnt[i]>=3)

		{

			for (int j=0;j<=i;++j)

				printf("%c",s[j]);

			return 0;

		}

	}

	printf("Just a legend");

	return 0;

}

巴特西

Codeforces 126B. Password（KMP，DP）

最新文章

热门文章