题意：

找一个01串中出现次数大于1的字串。01串长度≤3000

题解：

有个结论：一个串的所有后缀的所有前缀对应了这个串的字串。所以将这个串的所有后缀插入trie，累计经过trie上每个节点的经过次数，找到大于1的输出即可。

代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #define inc(i,j,k) for(int i=j;i<=k;i++) 5 #define maxn 3010 6 using namespace std; 7  8 int n,ch[maxn*maxn][2],sm[maxn*maxn],tot; char s[maxn]; 9 void insert(int x){10     int y=0;11     inc(j,x,n){12         if(!ch[y][s[j]-'0'])tot++,ch[y][s[j]-'0']=tot,y=tot;else y=ch[y][s[j]-'0']; sm[y]++;13     }14 }15 void print(int x){16     if(sm[x]>1)printf("%d\n",sm[x]);17     if(ch[x][0])print(ch[x][0]); if(ch[x][1])print(ch[x][1]);18 }19 int main(){20     scanf("%d",&n); scanf("%s",s+1); inc(i,1,n)insert(i);21     if(ch[0][0])print(ch[0][0]); if(ch[0][1])print(ch[0][1]); return 0;22 }
       
      
     

 

20160813