字符串：zoj 1905 || poj 2406 Power Strings

【转】http://www.slyar.com/blog/poj-2406-c.html

 

#include <stdio.h>
#include <string.h>
 
#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;
}