寒假集训比赛错题——Password

Asterix,Obelix和他们的临时伙伴Suffix、Prefix已经最终找到了和谐寺。然而和谐寺大门紧闭,就连Obelix的运气也没好到能打开它。

不久他们发现了一个字符串S(|S|<=1000000),刻在和谐寺大门下面的岩石上。Asterix猜想那一定是打开寺庙大门的密码,于是就大声将字符串朗读了出来,然而并没有什么事发生。于是Asterix又猜想密码一定是字符串S的子串T。

Prefix认为T是S的前缀,Suffix认为T是S的后缀,Obelix却认为T应该是S中的某一部分,也就是说,T既不是S的前缀,也不是S的后缀。

Asterix选择子串T来满足所有伙伴们的想法。同时,在所有可以被接受的子串变形中,Asterix选择了最长的一个(因为Asterix喜欢长的字符串)当Asterix大声读出子串T时,寺庙的大门开了。 (也就是说,你需要找到既是S的前缀又是S的后缀同时又在S中间出现过的最长子串)

现在给你字符串S,你需要找到满足上述要求的子串T。

题目类型:KMP,字符串

解题目标:找到最大的符合要求的子序列,使其既是前缀又是后缀,同时在字符串中间出现;

解题思路:1.用一遍KMP获得最长的前缀和后缀。

                  2.寻找在字符串的真子串(少最后几位)中最长的前缀和后缀长度,并记录,实际上是在找前缀和中间字串相等的最大长度;

                  3.从最大前缀长度为起点开始,如果当前能跳跃的最大距离 > z最大前缀与中间字串的长度,说明还未找到答案,因为答案应当是min(最长的前缀和后缀长度, 最长前缀与中间字串的长度),因此利用j = ne[j]得到下一个跳跃跨度并且继续比较,直到出线一个跳跃跨度 <= 最大前缀与中间字串的长度时,跳出,从头开始遍历长度为当前这个跳跃跨度长度的字符串输出;

AC代码:
 

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
 int ne[N];
int main()
{
	string a;
	cin>>a;
	int len = a.length();
	a = ' '+a;

		for(int i = 2, j = 0; i<=len; i++)
		{
			while(j && a[i] != a[j+1]) j = ne[j];
			if(a[i] == a[j+1]) j++;
			ne[i] = j;
		}
	
		//int maxn = *max_element(ne+2,ne+len);//我也不明白,为啥用这句会RE,我寻思着我也没写错,离谱
		int maxn = 0;
		for(int i = 2; i<=len-1; i++) if(maxn < ne[i]) maxn = ne[i];
		
		int j = ne[len];
		while(j > maxn) j = ne[j];
		
		if(j == 0)
		{
			cout<<"Just a legend"<<endl;
		}else 
		{
			for(int i = 1; i<= j; i++) cout<<a[i];
		}
	
	return 0;
}

上一篇:CentOS7安装MySQL,python3


下一篇:javaWeb学习JDBC