這個(gè)題是求一個(gè)字符串的最小重復(fù)單元的重復(fù)次數(shù)，那么求出最小重復(fù)單元的長(zhǎng)度即可。
這個(gè)題有3種方法，方法一：直接枚舉長(zhǎng)度為[1,len/2]內(nèi)的子串，暴力就過了。方法二：
將原串重復(fù)一次形成一個(gè)新串，用原串去匹配新串，但是得從第二個(gè)位置開始匹配，第一次
成功匹配的位置減一就代表最小重復(fù)單元的長(zhǎng)度。方法三：利用kmp的next函數(shù)，如果len
能夠整除len-next[len]，那么len-next[len]就代表最小重復(fù)單元的長(zhǎng)度。
方法一明顯是對(duì)的，數(shù)據(jù)不強(qiáng)的情況下就能水過了。方法二也不是那么容易想到的，不過
將原串?dāng)U展為2倍的做法也不是太奇葩，比如判斷2個(gè)循環(huán)串是否相等就可以用這個(gè)辦法做。
方法三就比較難理解了。
方法三的理解：
next[len]代表的是str的最長(zhǎng)前綴(使得這個(gè)前綴與同樣長(zhǎng)度的后綴相等)的長(zhǎng)度。所謂的next
數(shù)組就是長(zhǎng)度為1-len的str的滿足上述描述的最長(zhǎng)前綴的長(zhǎng)度。如果len是len-next[len]的倍數(shù)，
假設(shè)m = len-next[len] ，那么str[1-m] = str[m-2*m]，以此類推下去，m肯定是str的最小
重復(fù)單元的長(zhǎng)度。假如len不是len-next[len]的倍數(shù)， 如果前綴和后綴重疊，那么最小重復(fù)單元
肯定str本身了，如果前綴和后綴不重疊，那么str[m-2*m] != str[len-m,len]，所以str[1-m]
!= str[m-2*m] ,最終肯定可以推理出最小重復(fù)單元是str本身，因?yàn)橹灰粩噙f增m證明即可。
方法三的代碼如下：
#include <stdio.h>
#include <
string.h>
#include <algorithm>
using namespace std;
char szStr[1000010];
int nNext[1000010];
void GetNext(
char* szStr,
int nLen,
int* nNext)
{
nNext[0] = -1;
for (
int i = 1, j = -1; i < nLen; ++i)
{
while (j > -1 && szStr[i] != szStr[j + 1])
{
j = nNext[j];
}
if (szStr[i] == szStr[j + 1])
{
++j;
}
nNext[i] = j;
}
}
int main()
{
while (scanf("%s", szStr), strcmp(szStr, "."))
{
int nLen = strlen(szStr);
GetNext(szStr, nLen, nNext);
if (nLen % (nLen - nNext[nLen - 1] - 1))
{
printf("1\n");
}
else {
printf("%d\n", nLen / (nLen - nNext[nLen - 1] - 1));
}
}
return 0;
}