自动搬运

查看原文

来自洛谷，原作者为

	EternalAlexander 魔力的碎片都不再拥有的少年

搬运于2025-08-24 21:59:10，当前版本为作者最后更新于2018-06-23 11:40:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

写完看了下其他人代码，正解似乎是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;
}