Contents

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

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;
}

每天一句叨叨

没有自闭,何来爆爽!向自闭的日子致敬!