题解 P4341 【[BJWC2010]外星联络】

· · 题解

写完看了下其他人代码，正解似乎是SA。

但是既然n^2的Trie树简单应用可以过那还写啥后缀数组是吧。

直接暴力枚举子串，将trie树上对应位置的cnt值+1，最后先序遍历一遍就完了。因为子串只有n^2个，字符集大小为2，因此时空复杂度均为n^2。

n<=3000 n^2是肯定可以过的。

估计是最简单，代码最短的做法了。

#include <cstdio>

int ch[9000000][2]={0}; 
int cnt[9000000]={0};
int tail=0;
char s[4000];

int dfs(int root) {
    if (cnt[root]>1) printf("%d\n",cnt[root]);
    if (ch[root][0]) dfs(ch[root][0]);
    if (ch[root][1]) dfs(ch[root][1]);
    return 0;
}

int main() {
    int n;
    scanf("%d %s", &n, &s);
    for (int i=n;i>=1;--i) s[i]=s[i-1];
    for (int i=1;i<=n;++i) {
        int p=0;
        for (int j=i;j<=n;++j) {
            if (!ch[p][s[j]-'0']) ch[p][s[j]-'0']=++tail;
            p=ch[p][s[j]-'0']; cnt[p]++;
        }
    }dfs(0);
    return 0;
}