POJ 2752 Seek the Name, Seek the Fame

最新推荐文章于 2021-12-13 14:38:22 发布

原创最新推荐文章于 2021-12-13 14:38:22 发布

· 351 阅读

0 ·

版权

文章标签：

#Seek the Name #Seek the Fame POJ -

KMP 专栏收录该内容

2 篇文章

订阅专栏

原题：

Seek the Name, Seek the Fame

原题意思：输入一串全为小写字母的字符串，字符串长度小于400000，输出所有满足前缀和后缀相等的字符的长度，这个”组合条件“我会在样例中说明。

第一组样例解释：

样例一：ababcababababcabab  2：ababcababababcabab  4:ababcabababcabab  9:ababcabab ababcabab 18: 全部

样例二：aaaaa   1 2 3 4 5 不再一一解释；

     一开始我想的是直接运用string的substr函数代码如下：

     	while(cin>>str)
	{
		for(int i=0;i<str.length();i++)
		{
			s1=str.substr(0,i+1);
			s2=str.substr(str.length()-i-1,str.length());
			if(s1==s2)
			cout<<s1.length()<<" ";
		}
		cout<<endl;
	}

       答案是肯定的：Time Limit Exceeded   所以要找一种时间复杂度更短的算法，我不想再铤而走险，

       暴力救不了中国人，只能学习新的知识，KMP算法：

              KMP算法的核心思想是利用已经得到的部分匹配信息来进行后面的匹配过程。

             这里有一个很好的关于KMP的转载：http://blog.csdn.net/lin_bei/article/details/1252686

             附上神奇的代码，KMP：

 
#include<cstdio>
#include<string>
#include<string.h>
#include<iostream>
using namespace std;
int next[400005],a[400005];
string str;
int v[400005];


void Get_next()
{
	int t = -1,j = 0;
	next[0] = -1;
	while(j < str.length())
	{
		if(t == -1||str[j] == str[t])
		{
			j++; t++;
			next[j] = t;
		}
		else
		t = next[t];
	}
}
int main()
{
	int t;
	while(cin>>str)
	{
		t=0;
		memset(v,0,sizeof(v));
		Get_next();
		int j = next[str.length()];
		while(j > 0)
		a[t++] = j , j = next[j];
		for(int i = t-1; i >= 0; i--)
		cout<<a[i]<<" ";
		cout<<str.length()<<endl;
	}
	return 0;
}