文章作者：姜南(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学习心得，可以适当参考。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#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; } |