【题目链接】
【算法】
KMP
和POJ2406很像
【代码】
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cerrno>
#include <clocale>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <limits>
#include <list>
#include <map>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <utility>
#include <vector>
#include <cwchar>
#include <cwctype>
#include <stack>
#include <limits.h>
using namespace std;
#define MAXL 1000010 int i,n,TC;
char s[MAXL];
int next[MAXL]; template <typename T> inline void read(T &x) {
int f = ; x = ;
char c = getchar();
for (; !isdigit(c); c = getchar()) { if (c == '-') f = -f; }
for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';
x *= f;
} template <typename T> inline void write(T x) {
if (x < ) { putchar('-'); x = -x; }
if (x > ) write(x/);
putchar(x%+'');
} template <typename T> inline void writeln(T x) {
write(x);
puts("");
} inline void getnext() {
int i,pos;
next[] = ;
for (i = ; i <= n; i++) {
pos = next[i-];
while (pos > && s[pos+] != s[i]) pos = next[pos];
if (s[pos+] == s[i]) next[i] = pos + ;
else next[i] = ;
}
} int main() { while (true) {
read(n);
if (!n) return ;
scanf("%s",s+);
getnext();
printf("Test case #%d\n",++TC);
for (i = ; i <= n; i++) {
if (i % (i - next[i]) == && i / (i - next[i]) > ) printf("%d %d\n",i,i/(i-next[i]));
}
puts("");
} return ; }