【题解】POJ-2406 Power Strings

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).

输入

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.

输出

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

样例输入

abcd
aaaa
ababab
.

样例输出

1
4
3

提示

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

思路

KMP求最小循环节。输出最小循环周期。POJ提交时注意C++和G++的区别。

代码

char t[mxn];
int nxt[mxn];

void getnxt(char* t, int m)
{
    int i = 0, j = -1; nxt[0] = -1;
    while (i < m)
    {
        if (j == -1 || t[i] == t[j]) {
            i++, j++;
            // if (t[i] == t[j])
            //     nxt[i] = nxt[j]; // next数组优化
            // else
                nxt[i] = j;
        } else
            j = nxt[j];
    }
}

int main()
{
    while(scanf("%s", t) && strcmp(t, "."))
    {
        int m = strlen(t);
        getnxt(t, m);

        int L = m-nxt[m];   // 最小循环节=原串长度-末位失配，L=len-next[len]
        printf("%d\n", m%L ? 1 : m/L);  // 循环周期T=len/L
    }
    return 0;
}