Power Strings Time Limit:5s Memory limit:32M Accepted Submit:166 Total Submit:491 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). Each test case is a line of input representing s, a string of printable characters. For each s you should print the largest n such that s = a^n for some string a. 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. Sample Inputabcd aaaa ababab . Sample Output1 4 3   #include <stdio.h>#include <string.h> char s[1000001];short next[1000000]; int main(){    int i, j, len;     while (1)    {        scanf("%s", s);        if ('.' == s[0] && '\0' == s[1])            break;         len = strlen(s);        i = 0;        j = -1;        next[0] = -1;        while (i < len)        {            if (-1 == j || s[i] == s[j])            {                ++i;                ++j;                if (s[i] != s[j])                    next[i] = j;                else                    next[i] = next[j];            }            else                j = next[j];        }        i -= j;        if (0 == len % i)            i = len / i;        else            i = 1;        printf("%d\n", i);    } return 0;}

评论