[洛谷P4341][BJWC2010]外星联络

题目大意：给你一个长度为$n(n\leqslant3\times10^3)$的字符串，要你求出其中出现次数大于$1$的子串，并按字典序输出次数。

题解：建$SAM$后求出每个点的$size$，最后按字典序$dfs$一遍即可，这题$n$这么小，直接$O(n^2)$在$trie$上把每个点经过次数求出来，深搜即可。

卡点：无

C++ Code：

#include <cstdio>

#include <cstring>

#define maxn 3005

#define N (maxn * maxn)

int n, nxt[N][2], cnt[N], idx;

char s[maxn];

void insert(char *s) {

	static int rt; rt = 0;

	for (; *s; ++s) {

		int &nxt = ::nxt[rt][*s & 1];

		if (!nxt) nxt = ++idx;

		++cnt[rt = nxt];

	}

}

void dfs(int rt) {

	if (cnt[rt] > 1) printf("%d\n", cnt[rt]);

	if (nxt[rt][0]) dfs(nxt[rt][0]);

	if (nxt[rt][1]) dfs(nxt[rt][1]);

}

int main() {

	scanf("%d%s", &n, s);

	for (int i = 0; i < n; ++i) insert(s + i);

	dfs(0);

	return 0;

}