首页 > 代码库 > POJ--2752--Seek the Name, Seek the Fame【KMP】
POJ--2752--Seek the Name, Seek the Fame【KMP】
链接:http://poj.org/problem?id=2752
题意:对于一个字符串S,可能存在前n个字符等于后n个字符,从小到大输出这些n值。
思路:这道题加深了对next数组的理解。next[i+1]相当于以第i位结尾的长度为next[i+1]的子串与前next[i+1]个字符组成的子串相同,理解之后就比较好做了,首先字符串的长度len肯定是一个答案,然后next[len]也是一个答案,原因如红字所写,如此迭代直到next下标值等于0停止,这是从大到小得到了答案,再反序输出即可。
因为这道题的特殊性,用优化的getnext函数无法AC。
#include<cstring> #include<string> #include<fstream> #include<iostream> #include<iomanip> #include<cstdio> #include<cctype> #include<algorithm> #include<queue> #include<map> #include<set> #include<vector> #include<stack> #include<ctime> #include<cstdlib> #include<functional> #include<cmath> using namespace std; #define PI acos(-1.0) #define MAXN 500100 #define eps 1e-7 #define INF 0x7FFFFFFF #define LLINF 0x7FFFFFFFFFFFFFFF #define seed 131 #define mod 1000000007 #define ll long long #define ull unsigned ll #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 char str[401000]; int next[401000]; void getnext(){ int i = 0, j = -1; int l = strlen(str); next[0] = -1; while(i<l){ if(j==-1||str[i]==str[j]){ i++; j++; next[i] = j; } else j = next[j]; } } int ans[401000]; int main(){ int i,j; while(scanf("%s",str)!=EOF){ getnext(); int l = strlen(str); int i = l; int sum = 0; while(i!=0){ ans[sum++] = i; i = next[i]; } printf("%d",ans[sum-1]); for(i=sum-2;i>=0;i--){ printf(" %d",ans[i]); } puts(""); } }
POJ--2752--Seek the Name, Seek the Fame【KMP】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。