void dfs2(int x){
if (vis[x]) return;
vis[x] = 1;
for (int i = 0;i <= 1;i++){
if (sam.ch[x][i]){
// cout<<sam.ch[x][i]<<endl;
if (dp[sam.ch[x][i]] > 1) printf("%d\n",dp[sam.ch[x][i]]);
dfs2(sam.ch[x][i]);
}
}
vis[x] = 0;
}
这里不加vis记录就会T,底下是完整代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define B cout<<"Breakpoint"<<endl;
#define O(x) cout<<#x<<" "<<x<<endl;
#define o(x) cout<<#x<<" "<<x<<" ";
using namespace std;
int read(){
int x = 1,a = 0;char ch = getchar();
while (ch < '0'||ch > '9'){if (ch == '-') x = -1;ch = getchar();}
while (ch >= '0'&&ch <= '9'){a = a*10+ch-'0';ch = getchar();}
return x*a;
}
const int maxn = 6005;
int dp[maxn];
struct SAM{
int len[maxn],ch[maxn][30],fa[maxn];
int tot,lastNode;
SAM(){tot = lastNode = 1;}
void add(int c){
int preNode = lastNode;
int nowNode = lastNode = ++tot;
dp[nowNode] = 1,len[nowNode] = len[preNode]+1;
for (;preNode&&!ch[preNode][c];preNode = fa[preNode]) ch[preNode][c] = nowNode;
if (!preNode) fa[nowNode] = 1;
else{
int tmpNode = ch[preNode][c];
if (len[tmpNode] == len[preNode]+1) fa[nowNode] = tmpNode;
else{
int tmpNode1 = ++tot;
len[tmpNode1] = len[tmpNode],fa[tmpNode1] = fa[tmpNode];
for (int i = 0;i <= 1;i++) ch[tmpNode1][i] = ch[tmpNode][i];
len[tmpNode1] = len[preNode]+1;
fa[tmpNode] = fa[nowNode] = tmpNode1;
for (;preNode&&ch[preNode][c] == tmpNode;preNode = fa[preNode]) ch[preNode][c] = tmpNode1;
}
}
}
}sam;
struct node{
int to[maxn],nxt[maxn],head[maxn],tot;
node(){tot = 0;memset(head,0,sizeof(head));}
void add(int u,int v){
to[++tot] = v,nxt[tot] = head[u],head[u] = tot;
}
}ed1,ed2;
int n;
void dfs(int x){
for (int i = ed1.head[x];i;i = ed1.nxt[i]){
int to = ed1.to[i];
dfs(to);
dp[x] += dp[to];
}
}
bool vis[maxn];
void dfs2(int x){
if (vis[x]) return;
vis[x] = 1;
for (int i = 0;i <= 1;i++){
if (sam.ch[x][i]){
// cout<<sam.ch[x][i]<<endl;
if (dp[sam.ch[x][i]] > 1) printf("%d\n",dp[sam.ch[x][i]]);
dfs2(sam.ch[x][i]);
}
}
vis[x] = 0;
}
char s[maxn];
int main(){
n = read();
scanf ("%s",s+1);
for (int i = 1;i <= n;i++) sam.add(s[i]-'0');
for (int i = 1;i <= sam.tot;i++) ed1.add(sam.fa[i],i);
dfs(1),dfs2(1);
return 0;
}