POJ 2406 Power Strings C语言版

文章作者：姜南(Slyar) 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。

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

Slyar:说一下题目大意。a是一个字符串，记s=a^n为a重复n次所形成的字符串。比如说a是abcd，那么当n=3时，a^3就是abcdabcdabcd。现在给出字符串s，求出最大的重复次数n。

本题利用的还是KMP模式匹配算法，当然你需要真正理解Next[i]的含义才可以自己写出代码，我在这里纠结了很久…

这里有一篇我写的KMP学习心得，可以适当参考。

//www.slyar.com/blog/kmp.html

#include 
#include 

#define MAX 1000001

int next[MAX];
char s[MAX];

int main()
{
    int i, j, n, k, len;
    while(1)
    {
        scanf("%s", s);
        if (strcmp(s, ".") == 0) break;
        len = strlen(s);
        i = 0;
        j = -1;
        next[0] = -1;
        while(i < len)
        {
            if (j == -1 || s[i] == s[j])
            {
                i++;
                j++;
                next[i] = j;
            }
            else
            {
                j = next[j];
            }
        }
        /* 计算首尾重复子串的长度 */
        j = i - next[i];
        printf("%d %d %d\n", i, next[i], j);
        /* 若串满足重复性质，则i%j==0；否则重复子串为本身 */
        if (i % j == 0) k = i / j;
        else k = 1;
        printf("%d\n", k);
    }
    return 0;
}

转载请注明：Slyar Home » POJ 2406 Power Strings C语言版