poj_2406 KMP寻找重复子串问题

B - Power Strings

%I64d & %I64u

Description

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.

又是纯KMP算法

昨晚太晚了，浏览了下题目，就好困，然后就睡觉去了

今天早上坐公交的时候开始想了下这个题目，就想出来做法了。（PS.长沙周一上班高峰，公交真TM挤。地铁遥遥无期啊）。

做法如下：

只需用KMP算法求出next数组值，这个具体求法我昨晚的日志写的很清晰。

在求的过程中，用一个变量记录最新的失配处的位置，这样，初始点到失配点的字符串，即为重复母串，比如ababab，从第三位到最后一位均可匹配，因此失配点即为第二位，b。。因此结果就是总位数6/2=3；

当然之前想简单了，比如abababa，如果按上述做法，也会输出3.因为它的next值为0012345，明显失配处好像是第二位。。。实则要加入判断条件：如果总位数%重复母船长度！=0，则重复母串不存在，直接输出1.

#include <iostream>
#include <cstdio>
using namespace std;
char str[1000005];
int next[1000005];
int knext()
{
    int mini=0;
    next[0]=0;
    int i,j=0;
    for (i=1;str[i]!='

poj_2406 KMP寻找重复子串问题

相关推荐