时间限制：2s 空间限制：512MB
Background
在南极旅游的过程中 ATP意识到南极地区有丰富的淡水资源， 于是决定在南极建立淡水工厂，
向全世界供应冰冰凉的淡水来赚大钱！
它成功地说服了 zyf2000 和 cloverhxy 作为投资人， 很快一家规模宏大的工厂就轰隆隆地开工
了。工厂雇佣彩色的北极熊作为工人（工熊） ，利用北极熊锋利的牙齿把冰山啃下来，装在
瓶子里运到世界各地。
正在 ATP 的生意越做越大的时候，突然有一个自称税务官的亚马孙土著人来到了南极要对
ATP收税！可是 ATP 工厂的收益都买吃的了！怎么办！这个时候 zyf2000 想出了办法……
zyf2000 在参观工厂的时候发现，北极熊们皮毛的颜色种类如果细分下去还真是多！比如绿
色北极熊就有淡绿，草绿，墨绿和原谅绿多种。大约有 26 种不同的颜色。ATP 它们决定让
每只工熊剪下一点柔软的毛，给不习惯寒冷的税务官做一条长长的围巾！税务官拿到围巾以
后很感动，同意宽限一些缴税的时日。同时，他对这条围巾产生了兴趣……
Description
这条围巾的颜色分布可以描述为一个长度为 n 的只包含字母 A..Z 的字符串。税务官想知道
的问题很简单，他定义颜色串 S 的一个 goodstr为既是 S 的前缀也是 S 的后缀的字符串。对
于 S 的所有 goodstr，他想知道它们的长度分别是多少，以及它在 S 中分别出现了几次。
Input
只有一行一个仅由大写字母构成的字符串 S。
Output
第一行一个数 k代表 S 串的 goodstr个数；
接下来 k行，每行两个数字 a 和 b 描述一个 goodstr，a 代表它的长度，b代表它在 S 中的出
现次数。要求按照 a为关键字从小到大输出。显然每个不同的 goodstr的 a 值互不相同。
注意：goodstr包括这个字符串本身。
Sample Input
ABACABA
Sample Output
3
1 4
3 2
7 1
分析：
学姐的hu测题
学姐：真·送分题
这道题我一看
KMP+AC自动机
结果T三个点
正解：KMP+DP？（乱搞）
首先求出一个准确的t数组
（我一般喜欢用t，就是KMP数组，无所谓叫什么啦）
之后有一个递推式可以计算出答案
我们从字符串的最后向前统计答案
cnt[t[i]]+=cnt[i]
解释一下：
因为t中记录的都是当前最长的前缀及后缀，
所以某串的前后一定是一样的，
这就像一个简陋版的AC自动机，
只要长串出现过，那么ta的失配一定出现过
这里写代码片
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int N=100005;
int t[N];
int ch[N][27],len,tot=0;
char s[N];
int word[N],cnt[N],tt;
void doit()
{
int i,j;
len=strlen(s);
t[0]=-1;
for (i=0;i<len;i++)
{
int x=t[i];
while (x!=-1&&s[i]!=s[x]) x=t[x];
t[i+1]=++x;
cnt[i]=1;
}
cnt[len]=1;
return;
}
void solve()
{
int i,j,now=0;
for (i=len;i>=0;i--)
cnt[t[i]]+=cnt[i];
int f=t[len];
while (f)
{
word[++word[0]]=f;
f=t[f];
}
printf("%d
",word[0]+1);
for (i=word[0];i>=1;i--)
printf("%d %d
",word[i],cnt[word[i]]);
printf("%d 1",len);
return;
}
int main()
{
freopen("factory.in","r",stdin);
freopen("factory.out","w",stdout);
scanf("%s",&s);
doit();
solve();
return 0;
}