首页 > 代码库 > 字符串习题
字符串习题
poj 2406:
这道题出的很好，让我明白了kmp循环节的性质。不过，不知是我太弱，还是网上大牛太多，大家都是直接找到最小的循环节之后就直接判断它是否整除n了。我想了好久，一直不明白一个问题。
假设最小循环节的长度为D。如果存在长度为d的循环节，它满足d>D且d不是D的倍数，这种情况是怎么判断的（就是存在大于最小循环节且不是最小循环节倍数的循环节）。后来…发现如果存在的话，那么必然存在长度为gcd(d,D)的循环节…然后gcd(d,D)<D，于是就证明出不存在这种情况。
综上，所有的循环节的长度都必然是最短的循环节的长度的倍数。
1 //13365733 ooyyloo 2406 Accepted 5248K 125MS G++ 939B 2014-08-23 14:44:15 （第二次） 2 //13365580 ooyyloo 2406 Accepted 5248K 79MS G++ 772B 2014-08-23 14:21:11 3 #include <cstdlib> 4 #include <cstdio> 5 #include <algorithm> 6 #include <cstring> 7 #define rep(i, n) for (int i = 0; i < (n); i++) 8 #define FOR(i,l,r) for (int i = (l); i <= (r); i++) 9 using namespace std;10 const int maxn=1000001;11 12 int n;13 char str[maxn];14 int fail[maxn];15 int main(){16 for (; ; )17 {18 scanf("%s", str);19 if (str[0]==‘.‘) break;20 n = strlen(str);21 int j = 0;22 FOR (i, 2, n)23 {24 while (j && str[j] != str[i-1]) j = fail[j];25 if (str[j] == str[i-1]) j++;26 fail[i] = j;27 }28 /*j = fail[n];29 while (j && n % (n-j) != 0) j = fail[j];30 if (j == 0) printf("1\n");31 else printf("%d\n", n / (n - j));*/32 if (n % (n-j) == 0) printf("%d\n", n / (n - j));33 else puts("1");34 }35 return 0;36 }37 //第二次比第一次的时间复杂度的原因是poj评测机发烧...两种做法时间是一样的
字符串习题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。