SPOJ-LCS,SPOJ-LCS2-后缀自动机SAM专题训练_算法日常[20/100]

发表于 更新于 分类于 阅读次数：
SAM后缀自动机刷题笔记 SPOJ-LCS,SPOJ-LCS2-后缀自动机SAM专题训练 没有自闭，何来爆爽！向自闭的日子致敬！

LCS

题目链接

VJ上的LCS
spoj上的LCS

题意

给你两个串，求两个串的最长公共字串

解题思路

大佬:
对A建后缀自动机，然后用B去匹配，若能匹配上就转移到儿子，否则沿着parent树向上跳

我的补充:
先看当下B串中新加的字符x是否能通过上次匹配的后缀来转移，如果能转移就直接加，
否则就要跳到fa树上去匹配更短endpos为p的后缀(为了找到新加入的字符x的转移)，
然后在匹配到之后就是匹配到的长度+1(要加上刚进入的x字符的一个长度)

AC代码

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
#include<bits/stdc++.h>
using namespace std;
const int N=250010;
char s1[N],s2[N];
int ans;
struct sam{
    // 注意N是题目给的n的两倍,因为节点数最多有2*n-1个
      int p,q,np,nq,cnt,last,a[N<<1][26],l[N<<1],f[N<<1];
      sam(){cnt=0;last=++cnt;}
      void init(){
          cnt=0;last=++cnt;
          memset(a,0,sizeof(a));
          memset(l,0,sizeof(l));
          memset(f,0,sizeof(f));
      }
      void extend(int c){
            p=last;np=last=++cnt;l[np]=l[p]+1;
            while(!a[p][c]&&p)a[p][c]=np,p=f[p];
            if(!p)f[np]=1;
            else{
                  q=a[p][c];
                  if(l[p]+1==l[q])f[np]=q;
                  else{
                        nq=++cnt;l[nq]=l[p]+1;
                        memcpy(a[nq],a[q],sizeof(a[q]));
                        f[nq]=f[q]; f[np]=f[q]=nq;
                        while(a[p][c]==q)a[p][c]=nq,p=f[p];
                  }
            }
      }
      void solve(){
          init();
          scanf("%s",s1);scanf("%s",s2);
          int n=strlen(s1);
          for(int i=0;i<n;i++)extend(s1[i]-'a');
          ans = 0;n=strlen(s2);
          for(int i=0,p=1,tp=0;i<n;i++){
            int x = s2[i] - 'a';
            if(a[p][x]) tp++,p = a[p][x];
            else{
                for(;p&&!a[p][x];p=f[p]);
                if(!p) tp=0,p=1;
                else tp = l[p] + 1,p = a[p][x];
            }
            ans = max(ans,tp);
          }
          printf("%d\n",ans );
      }
}sam;
int T;
int main(){
    sam.solve();
    return 0;
}

LCS2

题目链接

VJ上的LCS2
spoj上的LCS2

题意

给你多个串，求他们的最长公共字串

解题思路

　　超级感谢大佬的博文

　　大佬的想法(果然就是多种值维护一下,但是我竟然没有勇气想下去…->弱鸡下次勇敢点):

　　poj2774或者就是LCS那道题，对一个串建立后缀自动机，另一个在上面匹配。

(下面的方法一在代码中有详细注释，建议复制代码后结合起来看)
　　这道题是对多个串求。那么同样，让每个串在后缀自动机上匹配，然后记录在后缀自动机的每个节点上记录，当前串在这个位置和第一个串的最大匹配数，h数组。

　　然后mn数组，每次对于这所有的节点的h取小，为从第2个串到现在所有的串，都能在这个节点上匹配的长度。

　　因为一旦某个节点匹配上了，那么它的父节点（parent树）的父节点都会匹配上（因为父节点是当前点的后缀），
　　所以按拓扑倒序，更新父节点的h，为父节点的len，（即最大长度）。

　　第二种写法是对n-1个字符串建立SAM，然后用最后一个串在n-1个串上匹配，每个自动机上都有一个当前的指针cur，当前答案ans。对最后一个串从头开始扫，求出最后一个串和每个串以当前字符结尾的最大匹配长度，在这里面取小，每次加入一个字符，可以直接判断cur的下一位，不需要从头开始。空间太大。

　　

　　总结:两种写法大同小异，只枚举举的顺序不同而已。

　　其实方法更简洁，更容易看懂，比解法一的缺点是多花了很多空间

方法一AC代码

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
// 方法一 80ms 25.6MB
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for (;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}

const int N = 100010;

struct Suffix_Automaton{
    int fa[N<<1], trans[N<<1][26], len[N<<1], Last, Index;
    int v[N], sa[N<<1], mn[N<<1], h[N<<1];
    char s[N];

    void extend(int c) {
        int P = Last,NP = ++Index;
        len[NP] = len[P] + 1;
        for (; P&&!trans[P][c]; P=fa[P]) trans[P][c] = NP;
        if (!P) fa[NP] = 1; //-
        else {
            int Q = trans[P][c];
            if (len[P] + 1 == len[Q]) fa[NP] = Q;
            else {
                int NQ = ++Index;
                fa[NQ] = fa[Q];
                len[NQ] = len[P] + 1;
                memcpy(trans[NQ], trans[Q], sizeof trans[Q]);
                fa[Q] = NQ;
                fa[NP] = NQ;
                for (; P&&trans[P][c]==Q; P=fa[P]) trans[P][c] = NQ;
            }
        }
        Last = NP;
    }
    void build() {
        Last = Index = 1;
        scanf("%s",s+1);
        int n = strlen(s+1);
        for (int i=1; i<=n; ++i) extend(s[i] - 'a');
        // index和第一个串s1的下标大致是对应的，但是中间还有克隆的节点
        for (int i=1; i<=Index; ++i) v[len[i]] ++;
        // 确实是只有n种长度..前缀的后缀-->所有的串-->所以只用n
        // 这里求前缀和只是为了下面能够求出排名数组,让他们按照深度占比权值(有点像权值线段树的那种)
        for (int i=1; i<=n; ++i) v[i] += v[i-1];
        // sa[i] 排名为i的节点。按深度排名（拓扑用）
        // i号节点按照它的len在v中前缀和减减--->其实就是排名,按照节点的长度(也就是深度)--->因为越深越长
        for (int i=1; i<=Index; ++i) sa[ v[len[i]]-- ] = i;
    }
    void calcc() {
        int n = strlen(s+1), now = 0, p = 1;
        memset(h, 0, sizeof(h));
        for (int i=1; i<=n; ++i) {
            int c = s[i] - 'a';
            if (trans[p][c]) p = trans[p][c], now ++;
            else {
                for (; p&&!trans[p][c]; p=fa[p]);
                if (!p) now = 0, p = 1;
                else now = len[p] + 1, p = trans[p][c];
            }
            h[p] = max(h[p], now);
        }
        // 拓扑倒序，parent树中从深度深的到浅的
        for (int i=Index; i>=1; --i) {
            int t = sa[i];
            mn[t] = min(mn[t], h[t]);
            // t节点有匹配,并且它的父节点(后缀link)不为源点--->那么让它的父节点的匹配值等于父节点的长度
            // 因为前面的操作是对最长的适配，所以没有管较短串的匹配,所以这里管一下
            // 但是为什么只对父节点，而不对更爷爷节点什么的呢，因为这个拓扑排序从底部向上，所以父节点在之后会出现
            // 所以爷爷节点由后面出现的父节点去管理就行了 ====》 太精妙了，amazing！
            if (h[t] && fa[t]) h[fa[t]] = len[fa[t]];
        }
    }
    void solve() {
        build();
        memset(mn, 0x3f, sizeof(mn));
        while (scanf("%s",s+1) != EOF) calcc();
        int ans = 0;
        for (int i=1; i<=Index; ++i) ans = max(ans, mn[i]);
        printf("%d",ans);
    }
}sam;

int main() {
    sam.solve();
    return 0;
}

方法二AC代码

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
// 方法二---N-1个自动机 130ms 175.1MB
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for (;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}

const int N = 200010;

struct SuffixAutomaton{
    int Last, Index, res, cur, fa[N], trans[N][26], len[N];
    SuffixAutomaton() {Last = Index = cur = 1; res = 0;}
    void extend(int c) {
        int P = Last, NP = ++Index;
        len[NP] = len[P] + 1;
        for (; P&&!trans[P][c]; P=fa[P]) trans[P][c] = NP;
        if (!P) fa[NP] = 1;
        else {
            int Q = trans[P][c];
            if (len[P] + 1 == len[Q]) fa[NP] = Q;
            else {
                int NQ = ++Index;
                fa[NQ] = fa[Q];
                len[NQ] = len[P] + 1;
                memcpy(trans[NQ], trans[Q], sizeof trans[Q]);
                fa[Q] = NQ;
                fa[NP] = NQ;
                for (; P&&trans[P][c]==Q; P=fa[P]) trans[P][c] = NQ;
            }
        }
        Last = NP;
    }
    int solve(int c) {
        if (trans[cur][c]) {cur = trans[cur][c]; res++; return res;}
        for (; cur&&!trans[cur][c]; cur=fa[cur]);
        if (!cur) res = 0, cur = 1;
        else res = len[cur] + 1, cur = trans[cur][c];
        return res;
    }
}sam[9];

char s[N];
char str[N>>1];

int main() {
    int n = 0,t = 0,len;
    scanf("%s",str+1);

    while (scanf("%s",s+1)!=EOF) {
        len = strlen(s + 1);
        for (int i=1; i<=len; ++i)
            sam[t].extend(s[i] - 'a');
        t ++;
    }
    int ans = 0;
    len = strlen(str+1);
    for (int i=1; i<=len; ++i) {
        int tmp = 1e9;
        for (int j=0; j<t; ++j)
            tmp = min(tmp, sam[j].solve(str[i] - 'a'));
        ans = max(ans, tmp);
    }
    printf("%d",ans);
    return 0;
}

每天一句叨叨

没有自闭，何来爆爽！向自闭的日子致敬！