首页 > 代码库 > poj 2406 Power Strings
poj 2406 Power Strings
题目链接：http://poj.org/problem?id=2406
思路：
1.理解Kmp算法的next数组的意义；
2.对于字符A[i]，i-next[i]等价于在字符串中存在一个长度为i-next[i]的重复子串；
3.当 i % (i - next[i]) == 0 等价于字符串由 (i/(i-next[i])) 个长度为 i - next[i]的子串连接组成;
代码：
#include <iostream>#include <string>using namespace std;const int MAX_N = 1000000 + 10;char S[MAX_N];int Next[MAX_N];int GetNext(char P[], int next[]){ int i = 0, j = -1; int len = strlen(P); if (len <= 0) return 0; next[0] = -1; while (i <= len) { if (j == -1 || P[i] == P[j]) next[++i] = ++j; else j = next[j]; }}int main(){ int len; int lenSubstr; while (scanf("%s", S) != EOF && strcmp(S, ".")) { len = strlen(S); GetNext(S, Next); lenSubstr = len - Next[len]; if (len % lenSubstr == 0) printf("%d\n", len / lenSubstr); else printf("1\n"); } return 0;}
poj 2406 Power Strings
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。