[POJ 2406] Power Strings【KMP】
Problem:
Time Limit: 3000MS | Memory Limit: 65536K |
Description
Input
Output
Sample Input
abcd aaaa ababab .
Sample Output
1 4 3
Hint
Source
Solution:
本题是 KMP 的变形,考查了自匹配 nxt[] 数组的性质。
设原串 s 长度为 len,令 k = len - nxt[len],则若 k | len,我们可以得到:
- ⇒ len = c * k (c ∈ N*),s1..(c-1)k == sk+1..ck
- ⇒ s1..k == sk+1..2k == …… == s(c-1)k+1..ck
即最大循环节数 c = len / k。否则若 k 不能整除 len,则 c = 1。
Code: O(T|s|) [5564K, 141MS]
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> using namespace std; char s[1000005]; int nxt[1000005]; int main(){ while(scanf("%s", s + 1) != EOF && s[1] != '.'){ int len = strlen(s + 1); nxt[1] = 0; for(register int i = 2, j = 0; i <= len; i++){ while(j && s[j + 1] != s[i]) j = nxt[j]; if(s[j + 1] == s[i]) j++; nxt[i] = j; } if(len % (len - nxt[len])) puts("1"); else printf("%d\n", len / (len - nxt[len])); } return 0; }
发表评论