hdu 5558 | 2015ACM/ICPC亚洲区合肥站 G Alice’s Classified Message (后缀自动机)

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5558

题意：

说了一大堆。。其实就是询问位置i开始的后缀和以位置[0…i – 1]开始的所有后缀中最大匹配的公共前缀长度

思路：

这个动态的过程很容易想到SAM啊。。

所以就一边匹配。。一边构建SAM就好了。。

需要注意的是，如果有多个最长，需要输出最左边的位置。

因此多维护一个leftmost,表示某个字符串第一次出现的结尾的位置。

 

C++
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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
 
 
 
/* ***********************************************
Author :111qqz
Created Time :2017年11月08日 星期三 18时50分18秒
File Name :4436.cpp
************************************************ */
 
#include <bits/stdc++.h>
#define PB push_back
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
 
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
#define MAXALP 30
struct state
{
    int len, link, nxt[MAXALP];
    int leftmost; //由于要求出现位置最小的，leftmost表示第一次出现的右端点位置。
};
const int N =1E5+7;
state st[N*2];
int sz, last,rt;
char s[N];
int cnt[2*N],rk[2*N];//for radix sort
void sa_init()
{
    sz = 0;
    last = rt = ++sz;
    st[1].len = 0;
    st[1].link=-1;
    ms(st[1].nxt,-1);
}
void sa_extend(int c,int head)
{
    int cur = ++sz;
    st[cur].len = st[last].len + 1;
    st[cur].leftmost = head;
    memset(st[cur].nxt, -1, sizeof(st[cur].nxt));
    int p;
    for (p = last; p != -1 && st[p].nxt[c] == -1; p = st[p].link)
        st[p].nxt[c] = cur;
    if (p == -1) {
        st[cur].link = rt;
    } else {
        int q = st[p].nxt[c];
        if (st[p].len + 1 == st[q].len) {
            st[cur].link = q;
        } else {
            int clone = ++sz ;
            st[clone].len = st[p].len + 1;
            st[clone].link = st[q].link;
            memcpy(st[clone].nxt, st[q].nxt, sizeof(st[q].nxt));
            st[clone].leftmost = st[q].leftmost;
            for (; p != -1 && st[p].nxt[c] == q; p = st[p].link)
                st[p].nxt[c] = clone;
            st[q].link = st[cur].link = clone;
        }
    }
    last = cur;
}
void topo()
{
    ms(cnt,0);
    for (int i = 1 ; i <= sz ; i++) cnt[st[i].len]++;
    for ( int i = 1 ; i <= sz ; i++) cnt[i]+=cnt[i-1];
    for (int i = 1 ; i <= sz  ;i++) rk[cnt[st[i].len]--] = i;
}
string S;
void solve (string S)
{
    sa_init();
    int n = S.length();
    int i = 0 ;
    while (i<n)
    {
    int now = rt;
    int len = 0 ;
    while (i<n &&st[now].nxt[S[i]-'a']!=-1)
    {
        now = st[now].nxt[S[i]-'a'];
        len++;
        sa_extend(S[i]-'a',i);
        i++;
    }
    if (!len)
    {
        sa_extend(S[i]-'a',i);
        printf("%d %d\n",-1,S[i]);
        i++;
    }
    else printf("%d %d\n",len,st[now].leftmost-len+1);
    }
}
 
 
int main()
{
#ifndef  ONLINE_JUDGE
        freopen("./in.txt","r",stdin);
#endif
 
    int T;
    int cas = 0 ;
    cin>>T;
    while (T--)
    {
        printf("Case #%d:\n",++cas);
        cin>>S;
        solve(S);
    }
 
 
#ifndef ONLINE_JUDGE  
    fclose(stdin);
#endif
    return 0;
}
 
 
 
 
 

 

 

 

作者： CrazyKK

ex-ACMer@hust，researcher@sensetime

说点什么

您将是第一位评论人！

提醒
wpDiscuz