首页 > 代码库 > POJ 2406 Power Strings KMP
POJ 2406 Power Strings KMP
题意：给你一个字符串，问你最多是由多少段相同的字串构成的
解题思路：求next指针的思路,我们匹配到 str[len],可以知道，len - str[len] 是他的循环节，再判断能不能整除就行了。
解题代码：
1 // File Name: 2406.cpp 2 // Author: darkdream 3 // Created Time: 2014年09月09日 星期二 20时15分59秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque>10 #include<stack>11 #include<bitset>12 #include<algorithm>13 #include<functional>14 #include<numeric>15 #include<utility>16 #include<sstream>17 #include<iostream>18 #include<iomanip>19 #include<cstdio>20 #include<cmath>21 #include<cstdlib>22 #include<cstring>23 #include<ctime>24 #define LL long long25 26 using namespace std;27 int next[1000005];28 char str[1000005];29 int len ; 30 void knext()31 {32 memset(next,0,sizeof(next));33 int j = 0 ; 34 int k = -1;35 next[0] = -1;36 while(j <= len )37 {38 if(k == -1 || str[j] == str[k]){39 j ++ ; 40 k ++ ;41 next[j] = k ; 42 }else{43 k = next[k];44 }45 }46 /* for(int i = 0 ;i <= len ;i ++)47 printf("%d ",next[i]);48 printf("\n");*/49 int t = next[len];50 if((len % (len -t) == 0 ) && (t % (len -t) == 0 ))51 printf("%d\n",len/(len-t));52 else printf("1\n");53 }54 int main(){55 while(scanf("%s",str) != EOF)56 {57 len = strlen(str);58 if(len == 1 && str[0] == ‘.‘)59 break;60 knext(); 61 }62 return 0;63 }
POJ 2406 Power Strings KMP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。