UVA 12012 - Detection of Extraterrestrial

题目链接

题意：给定一个字符串，求其所有子串中，对应1-n循环次数的最长串长度

思路：KMP，n才1000，可以接受O(n^2)的算法，对于每个后缀串，做一次KMP，然后在遍历一遍KMP数组，这样就可以得到每个子串的所有循环次数了，然后不断更新答案即可

代码：

#include 
#include 
#include 
using namespace std;

const int N = 1005;

int t, ans[N], n, l, r, m, next[N];
char str[N], s[N];

void getnext() {
    next[0] = next[1] = 0;
    int j = 0;
    for (int i = 2; i <= m; i++) {
	while (j && s[i - 1] != s[j]) j = next[j];
	if (s[i - 1] == s[j]) j++;
	next[i] = j;
    }
}

int main() {
    int cas = 0;
    scanf("%d", &t);
    while (t--) {
	memset(ans, 0, sizeof(ans));
	scanf("%s", str);
	n = strlen(str);
	for (int i = 0; i