BZOJ 2251 [2010Beijing Wc]外星联络 trie的本质以及字符串性质

题意:链接

方法: 字典树

解析:

zxr讲过的题，当时听好像就有一个什么神奇的结论，然后今天做的时候想了半天想起来是什么结论了，

对于一个字符串，它的所有后缀的所有前缀就能代表该串的所有子串。

然后呢，我们可以将所有的后缀都加到trie树里。end记录以某点为结尾的串出现多少次。

然后trie树之所以为字典树就是其从右往左走恰好是字典序，所以递归跑一遍输出满足题意的解。

另外，数组版需要开到n^2的空间复杂度，别问我为什么，不然你会各种RE,OLE，总会有神奇的数据将你卡住，所以最好老老实实开n^2。

代码:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 3010
using namespace std;
int n;
char s[N];
int son[N*N][3];
int end[N*N];
int tot;
void insert(char *s)
{
    int len=strlen(s),p=0;
    for(int i=0;i<len;i++)
    {
        if(!son[p][s[i]-'0'])son[p][s[i]-'0']=++tot;
        p=son[p][s[i]-'0'];
        end[p]++;
    }
}
void dfs(int rt)
{
    if(rt!=0&&end[rt]>1)printf("%d\n",end[rt]);
    if(son[rt][0])dfs(son[rt][0]);
    if(son[rt][1])dfs(son[rt][1]);
}
int main()
{
    scanf("%d",&n);
    scanf("%s",s+1);
    for(int i=1;i<=n;i++)
    {
        insert(s+i);
    }
    dfs(0);
}