题目描述

Description

小 P 在看过电影《超时空接触》(Contact)之后被深深的打动，决心致力于寻找外星人的事业。于是，他每天晚上都爬在屋顶上试图用自己的收音机收听外星人发来的信息。虽然他收听到的仅仅是一些噪声，但是他还是按照这些噪声的高低电平将接收到的信号改写为由 0 和 1 构成的串， 并坚信外星人的信息就隐藏在其中。他认为，外星人发来的信息一定会在他接受到的 01 串中重复出现，所以他希望找到他接受到的 01 串中所有重复出现次数大于 1 的子串。但是他收到的信号串实在是太长了，于是，他希望你能编一个程序来帮助他。

Input

输入文件的第一行是一个整数N ，代表小 P 接收到的信号串的长度。
输入文件第二行包含一个长度为N 的 01 串，代表小 P 接收到的信号串。

Output

输出文件的每一行包含一个出现次数大于1 的子串所出现的次数。输出的顺序按对应的子串的字典序排列。

Sample Input

7  
1010101   

Sample Output

3 
3 
2 
2 
4 
3 
3 
2 
2 

HINT

对于 100%的数据，满足 0<=N<=3000

题目分析

任意后缀都是某一个串的前缀
把所有后缀扔进trie树里,最后统计答案

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;

const int maxn=int(3e3)+11;
int n;
char s[maxn];
int cnt[maxn*maxn];
int to[maxn*maxn][4];
int tot;
void insert(int x)
{
    int now=0;
    for(int i=x;i<=n;i++)
    {
        if(!to[now][(s[i]-'0')]) to[now][(s[i]-'0')]=++tot;
        now=to[now][(s[i]-'0')],cnt[now]++;
    }
}
void dfs(int x)
{
    if(x&&cnt[x]>1) printf("%d\n",cnt[x]);
    if(to[x][0]) dfs(to[x][0]);
    if(to[x][1]) dfs(to[x][1]);
}
int main()
{   
    scanf("%d%s",&n,s+1);
    for(int i=1;i<=n;i++) insert(i);
    dfs(0);
    return 0; 
}