这个题是求一个字符串的最小重复单元的重复次数,那么求出最小重复单元的长度即可。这个题有3种方法,方法一:直接枚举长度为[1,len/2]内的子串,暴力就过了。方法二:将原串重复一次形成一个新串,用原串去匹配新串,但是得从第二个位置开始匹配,第一次成功匹配的位置减一就代表最小重复单元的长度。方法三:利用kmp的next函数,如果len能够整除len-next[len],那么len-next[len]就代表最小重复单元的长度。
方法一明显是对的,数据不强的情况下就能水过了。方法二也不是那么容易想到的,不过将原串扩展为2倍的做法也不是太奇葩,比如判断2个循环串是否相等就可以用这个办法做。
方法三就比较难理解了。
方法三的理解:
next[len]代表的是str的最长前缀(使得这个前缀与同样长度的后缀相等)的长度。所谓的next
数组就是长度为1-len的str的满足上述描述的最长前缀的长度。如果len是len-next[len]的倍数,假设m= len-next[len] ,那么str[1-m] = str[m-2 m],以此类推下去,m肯定是str的最小重复单元的长度。假如len不是len-next[len]的倍数, 如果前缀和后缀重叠,那么最小重复单元肯定str本身了,如果前缀和后缀不重叠,那么str[m - 2 m] != str[len-m,len],所以str[1-m]!= str[m - 2 * m] ,最终肯定可以推理出最小重复单元是str本身,因为只要不断递增m证明即可。

方法三的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#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;
}

版权声明:

本作品采用知识共享署名 2.5 中国大陆许可协议进行许可,欢迎转载,但转载请注明来自远行’s Life,并保持转载后文章内容的完整。本人保留所有版权相关权利。

本文链接:http://xiaopengcheng.top/2012/09/30/poj 2406 Power Strings kmp的妙用/