題干：

Given two strings a and b we define a*b to be their concatenation. For example, if a = "abc" and b = "def" then a*b = "abcdef". If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a^0 = "" (the empty string) and a^(n+1) = a*(a^n).

Input

Each test case is a line of input representing s, a string of printable characters. The length of s will be at least 1 and will not exceed 1 million characters. A line containing a period follows the last test case.

Output

For each s you should print the largest n such that s = a^n for some string a.

Sample Input

abcd aaaa ababab .

Sample Output

1 4 3

Hint

This problem has huge input, use scanf instead of cin to avoid time limit exceed.

?

題目大意：

? ?給出定義：字符串相乘"abc" * "def" = "abcdef"，給出冪運算的定義，

解題報告：

? ?裸的最小循環(huán)節(jié)。

AC代碼：

#include<set> #include<cstdio> #include<string> #include<cstring> #include<iostream> #define ll long long using namespace std; char s[1000005]; int next[1000005]; int len; void getnext() {int k = -1,j = 0;next[0]=-1;while(j<len) {if(k == -1 || s[j] == s[k]) {j++;k++;next[j]=k;}else k=next[k];} } int main() {while(~scanf("%s",s)) {if(s[0] == '.') break;memset(next,0,sizeof next);len = strlen(s);getnext();if(len % (len - next[len]) == 0) printf("%d\n",len/(len-next[len]));else puts("1");} return 0; }

總結：

1.注意那個else put("1")那里，要想清楚為什么會有這種情況發(fā)生。不光是因為? 沒有循環(huán)節(jié) 的情況（因為沒有循環(huán)節(jié)有的也是要進入那個if的，，因為next[len]可以只要不是起始位置，就最小是0啊，所以也可以進入if，比如"as"這個字符串）。如果是"asa"這樣的字符串就比較尷尬了，，想想為啥吧，，，，反正只有這類的情況才會進入else，，并不是所有沒有循環(huán)節(jié)的情況都是進入else的。。。其實看下面那個總結也可以看出來。，，就是 完全沒有循環(huán)節(jié)的? 是直接next[len]=0，但是如果有一部分循環(huán)節(jié)，那就比較尷尬了 。。。詳情看下面的那兩個例子。

2.舉兩個例子幫助理解一類新的問題：（這種就屬于沒有循環(huán)節(jié)的，但是如果想要湊成循環(huán)節(jié)，還需要加的單詞數(shù)）

abdabdab? len:8 next[8]:5

最小循環(huán)節(jié)長度：3（即abd）?? 需要補的個數(shù)是1? d

ababa? len:5 next[5]：3

最小循環(huán)節(jié)長度：2（即ab）??? 需要補的個數(shù)是1? b

符合?len% ( len- next[i] ) == 0 && next[len] != 0 ,?則說明字符串循環(huán)，而且

循環(huán)節(jié)長度為: ? len- next[i]

循環(huán)次數(shù)為: ? ? ? len/ ( len- next[i] )

總結

以上是生活随笔為你收集整理的【POJ - 2406】Power Strings （KMP，最小循环节）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。