题意：求一个01串中每个出现次数大于1的子串的个数
注意到\(n\leq3000\)，因此可以暴力在Trie上插入所有的后缀，统计end节点的个数
正确的姿势是枚举一个左端点\(l\)，然后一路插入\([l,n]\)，而不是枚举两个端点，那样是\(O(n^3)\)的
字典序？中序遍历输出即可
#include#include #include using namespace std;inline int rd(){ int ret=0,f=1;char c; while(c=getchar(),!isdigit(c))f=c=='-'?-1:1; while(isdigit(c))ret=ret*10+c-'0',c=getchar(); return ret*f;}#define pc putchar#define space() pc(' ')#define nextline() pc('\n')void pot(int x){if(!x)return;pot(x/10);pc('0'+x%10);}void out(int x){if(!x)pc('0');if(x<0)pc('-'),x=-x;pot(x);}const int MOD = 1e9+7;int add(int x,int y){return x+y>MOD?x+y-MOD:x+y;}int sub(int x,int y){return x-y<0?x-y+MOD:x-y;}int mul(int x,int y){return (long long)(1ll*x*y)%MOD;}void Add(int &x,int y){x=add(x,y);}void Sub(int &x,int y){x=sub(x,y);}void Mul(int &x,int y){x=mul(x,y);}const int SQRN=3005;const int MAXN = SQRN*SQRN;int ch[MAXN*2][2],ed[MAXN*2],tot,n;char s[SQRN];inline int newnode(){return ++tot;}void insert(int l){ int cur=0; for(int i=l;i<=n;i++){ int c=s[i]-'0'; if(!ch[cur][c]) ch[cur][c]=newnode(); cur=ch[cur][c];ed[cur]++; } }void dfs(int cur){ if(ed[cur]>1) out(ed[cur]),nextline(); if(ch[cur][0]) dfs(ch[cur][0]); if(ch[cur][1]) dfs(ch[cur][1]);}int main(){ n=rd(); scanf("%s",s+1); for(int i=1;i<=n;i++)insert(i); dfs(0); return 0;}