poj2106，D - Power Strings POJ - 2406

Given two strings a and b we define ab to be their concatenation. For example, if a = “abc” and b = “def” then ab = “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.

• 題意：定義一個算法，對于字符串a，aⁿ表示有n個a相連接。然后給你一個字符串s，找出一個盡可能大的n，能夠滿足aⁿ=s

• 解題思路：這個題我們可以用kmp的方法進行求解，具體的kmp請參考這篇博客 kmp詳解

  poj2106、這里講解一下用kmp的原理，kmp的原理首先是對字符串進行一個預處理一個next數組，這個數組表示的內容為如果當前位置i這個字符不匹配的話，那么直接匹配nex[i]的字符，因為i的前面和next[i]的前面是相同的。因此，我們對s進行預處理，如果只看最后一個位置的next[i]的值的話，那么字符串s的前next[i]長度的字符和后next[i]長度的字符是相同的。那么如果要是滿足一個n>1的情況下的話，一定存在s.length()/(s.length()-nex[s.length()],的余數是一個為0，并且那個字符串a即為s從頭開始長度為s.length()-nex[s.length()].
  證明：記c=s.length-nex[s.length()], len為字符串長;根據nex的原理我們可以知道s[0]=s[len-c-1],s[1]=s[len-c]…s[c]=s[len-1],所以a的長度便是c的值，我們假設如果存在a的長度大與c的話，那么為了滿足上面一些式子成立，a長度為c的答案也是一定成立的，而且a長度越小n越大。如果a的長度小于c的話，那么根據nex數組形成的原理，我們已經可以保證nexs.[length()]的長度比現在的長。證畢

代碼：

#include<iostream>
#include<string>
using namespace std;
const int inf = 1e6;
string s;
char sn[inf];
int p[inf];
int nex[inf];
void Getnex(){nex[0]=-1;int j=0,k=-1;while(j<s.size()){if(k==-1||s[k]==s[j]){j++;k++;nex[j]=k;}else k=nex[k];}
}
int main()
{	int cas=0;while(cin>>s){if(s==".")break;Getnex();int c=nex[s.size()];//cout<<c<<endl;//cout<<s.size()-c<<endl;if(s.size()%(s.size()-c)==0){cout<<s.size()/(s.size()-c)<<endl;}else cout<<"1"<<endl;}return 0;
}