poj 1509 Glass Beads (后缀自动机求最小循环表示)

2017-11-04 · 2 min read · 后缀自动机最小表示法

题意：

给定一个循环字符串，问字典序最小的串的开始位置。

思路：

字符串的最小表示法的复杂度是O(n)，代码也不是很难写，不过由于最近在学SAM,所以用SAM写了一下。

参照张天扬的论文：

把原串复制一遍到后面，然后构建后缀自动机。
从初始状态开始，每次走字典序最小的转移，走|S|之后得到的就是最小循环表示。
如果求的是最小后缀，就在原串后加入一个比字符集中所有字符的字典序都小的字符作为终止后，再添加一遍原串。

/* ***********************************************
Author :111qqz
Created Time :2017年11月03日 星期五 18时20分42秒
File Name :2774_SAM.cpp
************************************************ */

 1//#include <bits/stdc++.h>
 2#include <iostream>
 3#include <cstdio>
 4#include <algorithm>
 5#include <cmath>
 6#include <string>
 7#include <cstring>
 8#define PB push_back
 9#define fst first
10#define sec second
11#define lnxt l,m,rt<<1
12#define rnxt m+1,r,rt<<1|1
13#define ms(a,x) memset(a,x,sizeof(a))
14typedef long long LL;
15#define pi pair < int ,int >
16#define MP make_pair

1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;

const int maxn = 5E5;

 1struct node{
 2    node*nxt[26],*fail;
 3    LL len,cnt;
 4};
 5struct SAM{
 6    node no[maxn];
 7    node*root;
 8    int cnt;
 9    node*newnode(){
10    ms(no[cnt].nxt,0);
11    no[cnt].fail=NULL;
12    no[cnt].len = no[cnt].cnt = 0;
13    return &no[cnt++];
14    }
15    void init()
16    {
17    cnt = 0;
18    root = newnode();
19    }
20    SAM(){
21    cnt = 0;
22    root = newnode();
23    }
24    node*add(int c,node*p){
25        node*cur = newnode();
26        cur->len = p->len+1;
27        while(p&&!p->nxt[c]){
28            p->nxt[c] = cur;
29            p = p->fail;
30        }
31        if(!p){
32            cur->fail = root;
33            return cur;
34        }
35        node*q = p->nxt[c];
36        if(p->len+1==q->len){
37            cur->fail = q;
38        }else{
39            node*nq = newnode();
40            *nq = *q;
41            q->fail = cur->fail = nq;
42            nq->len = p->len+1;
43            while(p&&p->nxt[c]==q){
44                p->nxt[c] = nq;
45                p = p->fail;
46            }
47        }
48        return cur;
49    }
50    int calc(int L)
51    {
52    node *p =root;
53    for ( int i = 0 ; i < L ; i++)
54    {
55        bool flag = false;
56        for ( int j = 0 ; j < 26 ; j++) //找字典序最小的.
57        if (p->nxt[j])
58        {
59            flag = true;
60            p=p->nxt[j];
61            break;
62        }
63        if (!flag) break;
64    }
65    return p->len + 1 - L;
66    }
67};
68SAM sam;
69string A,B;
70int main()
71{
72    #ifndef  ONLINE_JUDGE 
73        freopen("./in.txt","r",stdin);
74  #endif
75    int T;
76    cin>>T;
77    while (T--)
78    {
79        sam.init();
80        node *cur =sam.root;
81        cin>>A;
82        for ( int i = 0 ; i < A.length() ; i++https://111qqz.com/wordpress/wp-admin/post-new.php#) cur = sam.add(A[i]-'a',cur);
83        for ( int i = 0 ; i < A.length() ; i++) cur = sam.add(A[i]-'a',cur);
84        int ans = sam.calc(A.length());
85        printf("%d\n",ans);
86    }

1  #ifndef ONLINE_JUDGE  
2  fclose(stdin);
3  #endif
4    return 0;
5}