POJ1509 Glass Beads

发表于

  题意:给你一个循环串(首尾相接)，求出使其字典序最小的起始位置。

  后缀自动机(SAM)的第一道题。
  看后缀自动机有关的东西看了很久，差不多明白了一些。
  这道题其实本来有更加简单的暴力做法，不过就全当练习SAM了。
  首先将原串S扩展至两倍SS，这是循环串的惯用套路。
  接着将SAM增量构造出来，由于SAM包含了原串的所有子串，所以在SAM上，每次沿着字典序最小的边走，走$|S|$次，到达节点u一定包含要找的字典序最小的串。
  那么如何将其提取出来?也就是，如何在u表示的众多串中，找到那个串，并且知道其在原串中的起始位置呢?
  其实并不用找到那个串。注意到u表示的最长的串一定是从原串的开头到我们要找的串的末尾的。而根据SAM的性质，我们要找的串一定是最长串的后缀，且长度为n。于是$Max[u]-n+1$便是答案了。
  要注意一点:SAM中是否有某个节点是用其对应下标是否为0来判断的。所以SAM的start节点不能设为0。为了方便，设为1即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
using namespace std;
#define rep(i, l, r) for(int i = l, i##end = r; i <= i##end; ++i)
#define drep(i, l, r) for(int i = l, i##end = r; i >= i##end; --i)
#define ms(a, b) memset(a, b, sizeof a)
const int maxn = 10010, SIZE = (maxn << 3), SIGMA = 26;
template<class T> inline bool chkmax(T& a, T b) { return a < b ? a = b, 1 : 0; }
template<class T> inline bool chkmin(T& a, T b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline T& read(T& x)
{
	static char c; bool flag = 0;
	while(!isdigit(c = getchar())) if(c == '-') flag = 1;
	for(x = c ^ 48; isdigit(c = getchar()); x = (x << 3) + (x << 1) + (c ^ 48));
	if(flag) x = -x; return x;
}
namespace SAM
{
    int cur, last;
    int ch[SIZE][SIGMA], next[SIZE], Max[SIZE];
    int New(int x) { Max[++cur] = x; return cur; }
    void init() { ms(next, 0); ms(Max, 0); ms(ch, 0); cur = last = 1; }
    void extend(int c)
    {
        int u = New(Max[last] + 1), v = last;
        for(; v && !ch[v][c]; v = next[v]) ch[v][c] = u;
        if(!v) next[u] = 1;
        else
        {
            int h = ch[v][c];
            if(Max[h] == Max[v] + 1) next[u] = h;
            else
            {
                int o = New(Max[v] + 1);
                memcpy(ch[o], ch[h], sizeof ch[h]);
                next[o] = next[h];
                next[h] = next[u] = o;
                for(; v && ch[v][c] == h; v = next[v]) ch[v][c] = o;
            }
        }
        last = u;
    }
}
using namespace SAM;
char s[maxn];
int n;
int main()
{
    freopen("exec.in", "r", stdin); freopen("exec.out", "w", stdout);
    int _; read(_);
    while(_--)
    {
        init();
        scanf("%s", s); n = strlen(s);
        rep(i, 0, n - 1) extend(s[i] - 'a');
        rep(i, 0, n - 1) extend(s[i] - 'a');
        int h = 1;
        rep(i, 1, n) rep(c, 0, 25)
            if(ch[h][c]) { h = ch[h][c]; break; }
        printf("%d\n", Max[h] - n + 1);
    }
    return 0;
}