BZOJ-2251: [2010Beijing Wc]外星联络

Description

他希望找到他接受到的 01 串中所有重复出现次数大于 1 的子串。但是他收到的信号串实在是太长了，于是，他希望你能编一个程序来帮助他。N<=3000

每个子串是母串的所有后缀的前缀。
那么就将母串的所有后缀扔进trie树中，路径节点个数+1，每个节点到根节点的串即为一个子串，dfs顺序即为字典序最小。
时间复杂度O(n^2)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
char s[4000];
int a[4000];
struct trie
{
    trie *c[2];
    int cnt;
    trie(){c[0]=c[1]=NULL; cnt=0;}
}*root=new trie();
void dfs(trie *p)
{
    if(!p||p->cnt<=1) return ;
    printf("%d\n",p->cnt);
    dfs(p->c[0]); dfs(p->c[1]);
}
int main()
{
    scanf("%d%s",&n,s);
    for(int i=0;i!=n;++i) a[i]=s[i]-'0';
    for(int i=0;i!=n;++i)
    {
        trie *p=root;
        for(int j=i;j!=n;++j)
        {
            if(!p->c[a[j]]) p->c[a[j]]=new trie();
            p=p->c[a[j]]; p->cnt++;
        }
    }
    dfs(root->c[0]); dfs(root->c[1]);
    return 0;
}