POJ 1509 循环同构的最小表示法

题目大意：

给定一个字符串，可以把一段尾部接到头部，这样找到一个最小的字符串

方案一：

利用循环同构中找最小表示的方法来解决

论文参考http://wenku.baidu.com/view/438cad13a2161479171128b6.html

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 
 5 using namespace std;
 6 #define N 10005
 7 char s[N];
 8 
 9 inline int minpos(char *s)
10 {
11     int l = strlen(s);
12     int i=0 , j=1 , k=0;
13     while(i<l&&j<l&&k<l){ //这里k<l是防止出现所有数都一样导致无限循环
14         if(i == j) j++;
15         else if(s[(i+k)%l]>s[(j+k)%l]){
16             i = i+k+1;
17             k=0;
18         }
19         else if(s[(i+k)%l]<s[(j+k)%l]){
20             j = j+k+1;
21             k=0;
22         }
23         else k++;
24     }
25     return min(i , j)+1;
26 }
27 
28 int main()
29 {
30    // freopen("a.in" , "r" , stdin);
31     int T;
32     scanf("%d" , &T);
33     while(T--)
34     {
35         scanf("%s" , s);
36         printf("%d
" , minpos(s));
37     }
38     return 0;
39 }

后缀自动机写法:

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <vector>
 5 #include <queue>
 6 using namespace std;
 7 /* run this program using the console pauser or add your own getch, system("pause") or input loop */
 8 #define M 26
 9 #define N 40100
10 char str[N];
11 
12 struct SamNode{
13     SamNode *son[M] , *f;
14     int l , s;
15 };
16 
17 struct Sam{
18     SamNode sam[N] , *root , *last;
19     int cnt;
20     
21     void init(){
22         cnt = 0;
23         memset(sam , 0 , sizeof(sam));
24         root = last = &sam[0];    
25     }
26     
27     void add(int x){
28         SamNode *p = &sam[++cnt] , *jp=last;
29         /*
30         这里p->s = jp->s+1写成p->s = p->l也是一样的，因为对于每次当前的last来说，
31         l和s的值是一样的，因为每次当前的last都是处于字符串的位置上的
32         数，不是额外添加的节点 
33         */ 
34         p->l = jp->l+1; p->s = jp->s+1;
35         last = p;
36         for(; jp&&!jp->son[x] ; jp=jp->f) jp->son[x] = p;
37         if(!jp) p->f=root;
38         else{
39             if(jp->l+1 == jp->son[x]->l) p->f = jp->son[x];
40             else{
41                 SamNode *r = &sam[++cnt] , *q = jp->son[x];
42                 *r=*q;
43                 r->l = jp->l+1 ; r->s = p->l;
44                 q->f = p->f = r;
45                 for(; jp && jp->son[x]==q ; jp=jp->f) jp->son[x]=r;
46             }
47         }
48     }    
49 }sam;
50 
51 int solve(int len)
52 {
53     SamNode *cur = sam.root;
54     for(int i=0 ; i<len ; i++){
55         for(int j=0 ; j<26 ; j++){
56             if(cur->son[j]){
57                 cur = cur->son[j];
58                 break;
59             }
60         }
61     }
62     return cur->s-len+1;
63 }
64 
65 int main(int argc, char *argv[]) {
66 //    freopen("in.txt" , "r" , stdin);
67 //    freopen("out.txt" , "w" , stdout);
68     int T;
69     scanf("%d" , &T);
70     while(T--){
71         scanf("%s" , str);
72         int len = strlen(str);
73         sam.init();
74         for(int i=0 ; i<len ; i++)
75             str[len+i] = str[i];
76         for(int i=0 ; i<len*2 ; i++)
77             sam.add(str[i]-'a');
78         int ret = solve(len);
79         printf("%d
" , ret);
80     }
81     return 0;
82 }