_WA自动机的blog

过期高中生。

永远做不动的SAM题

发表于 阅读次数： Valine：

SAM为什么是神？在讨论这个问题之前，我们先讨论一下其他字符串数据结构相对于SAM究竟差在什么地方。

乐曲主题

大意：给定字符串，求最长的重复子串（必须存在两次重复不重叠）

题解：首先建立SAM。对于SAM上每个结点，若其\(|\mathrm{endpos}|\ge 2\)，则出现至少两次。如果要求不重叠，则第一次和最后一次出现之间的长度应该不小于该子串长。这样，我们需要对于每个结点求其\(\mathrm{endpos}\)集合的最小值和最大值。考虑\(\mathrm{parent}\)树，父亲的\(\mathrm{endpos}\)包含所有子节点的\(\mathrm{endpos}\)（如果父亲是np类结点，则自己还会有独有的一个\(\mathrm{endpos}\)）。所以最小值最大值可以在树上递推得到。

需要注意，因为操作的是差分序列，所以要处理一些边界情况。

代码：

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
#include <cstdio>
#include <cstring>

const int N=50000+100;
const int INF=1004535809;

int ch[N][176];
int mx[N],right[N];
int parent[N];
int s[N],t[N];
int c[N],id[N];
int siz[N];
int mipos[N],mxpos[N];
int last=1,cnt=1;

template<class T>inline T max(T a,T b){return a<b?b:a;}
template<class T>inline T min(T a,T b){return a<b?a:b;}

void insert(int c,int k)
{
    int p=last,np=last=++cnt;
    mx[np]=mx[p]+1;
    mipos[np]=mxpos[np]=k;
    right[np]=1;
    while (p && !ch[p][c]) ch[p][c]=np,p=parent[p];
    if (!p) {parent[np]=1;return;}
    int q=ch[p][c];
    if (mx[q]==mx[p]+1) parent[np]=q;
    else
    {
        int nq=++cnt;
        mx[nq]=mx[p]+1;
        memcpy(ch[nq],ch[q],sizeof(ch[q]));
        while (p && ch[p][c]==q) ch[p][c]=nq,p=parent[p];
        parent[nq]=parent[q];parent[q]=parent[np]=nq;
    }
}

void radixsort(int n)
{
    for (int i=1;i<=cnt;++i) ++c[mx[i]];
    for (int i=1;i<=n;++i) c[i]+=c[i-1];
    for (int i=cnt;i;--i) id[--c[mx[i]]]=i;
    for (int i=cnt-1;~i;--i) right[parent[id[i]]]+=right[id[i]]; 
    for (int i=cnt-1;~i;--i) 
    {
        mipos[parent[id[i]]]=min(mipos[parent[id[i]]],mipos[id[i]]);
        mxpos[parent[id[i]]]=max(mxpos[parent[id[i]]],mxpos[id[i]]);
    }
    int ans=0;
    for (int i=cnt;i;--i)
        if (mxpos[i]^mipos[i]) ans=max(ans,min(mx[i],mxpos[i]-mipos[i]-1));
    if (ans>=4) printf("%d",ans+1);
    else puts("0");
}
 
int main()
{
    int n;
    scanf("%d",&n);
    for (int i=1;i<=n;++i) scanf("%d",s+i);
    for (int i=n;i;--i) s[i]=s[i]-s[i-1];
    for (int i=1;i<=2*n;++i) mxpos[i]=0,mipos[i]=n;
    for (int i=1;i<=n;++i) insert(s[i]+87,i);
    radixsort(n);
}