bzoj2251[2010Beijing Wc]外星联络*

bzoj2251[2010Beijing Wc]外星联络

题意：

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

题解：

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

代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 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
",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