SPOJ LCS Longest Common Substring (后缀自动机模板题)

Posted by 111qqz on Friday, November 3, 2017

TOC

题意:

给出2个字符串(2.5E5),问最长公共子串的长度。

思路:

拿一个串建SAM

由于SAM上的任何一个状态,都对应一个或者若干个子串,然后拿另一个串在SAM上面跑就行了

20171110UPdate:我好像说得太简略了。。

参考clj的冬令营讲稿:

  * 给两个长度小于100000的字符串A和B,求出他们的最长公共连续子串。 Ê我们构造出A的后缀自动机SAM
  * 对于SAM的每个状态s,令r为Right(s)中任意的一个元素,它代表的是结束位置在r的,长度在[Min(s),Max(s)]之间的所有子串。
  * 我们不妨对状态s,求出所有B的子串中,从任意r开始往前能匹配的最大长度L,那么min(L,Max(s))就可以更新答案了。
  * 我们考虑用_SAM_读入字符串_B_。
  * **令当前状态为_s_,同时最大匹配长度为_len _Ê我们读入字符_x_。如果_s_有标号为_x_的边,**
  * **那么_s=trans(s,x),len = len+1 _Ê否则我们找到_s_的第一个祖先_a_,它有标号为_x_的边,令**
  * **_s=trans(a,x),len=Max(a)+1__。 _Ê如果没有这样的祖先,那么令_s=root,len=0_。**
  * 在过程中更新状态的最大匹配长度

唯一不显然的地方在于,为什么当失配时,我们是沿着parent树向上找。

考虑如下例子:


我们知道,parent树,或者叫后缀链树,一个状态S指向的是,总起点开始到S的子串的后缀中,长度最长的后缀,满足该后缀所对应的某个状态Q(对应的意思是说,从初始状态到状态Q表示的子串恰好是该后缀)的right集合和状态S的集合不相等。

假设我们目前匹配到的状态表示的子串是abcbc,然后下一位要匹配的字母是b,而状态abcbc没有通过b转移的边(这些图上没有,我懒得画了orz)

这个时候考虑回退…对于abcbc的后缀,bcbc,cbc和abcbc面临的情况是一样的,因为bcbc,cbc,abcbc三个字符串的right集合相同,也就是出现的位置完全相同,那么既然abcbc没有通过b转移的边,bcbc,cbc也一定没有通过b转移的边。

这时候考虑转移到abcbc的par状态,也就是表示子串bc的状态,原因是bc的right集合和abcbc的right集合不同,更准确得说,bc的right集合是包含abcbc的right集合的。

而bc在之前匹配abcbc的时候,已经匹配过了,也就是说bc一定是可以匹配的,

如果此时bc有一条通过b转移的边,此时匹配的长度就变成了bc对应的状态所对应的max再+1

老年人的第一个SAM

关于SAM的笔记之后补。

用了动态的写法.

/* ***********************************************
Author :111qqz
Created Time :2017年11月03日 星期五 18时20分42秒hongchenzuoban
File Name :2774_SAM.cpp
************************************************ */

#include <bits/stdc++.h>
#define PB push_back
#define fst first
#define sec second
#define lnxt l,m,rt<<1
#define rnxt 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;
const int N=3E5;
struct SAM
{
    struct node
    {
        node *nxt[26],*fa;int len;
        node(int M) {len=M;fa=0;memset(nxt,0,sizeof(nxt));}
    };
    typedef node* P_node;
    P_node ro,lst;
    SAM() {ro=new node(0);lst=ro;}
    void Insert(char ch)
    {
        int ID=ch-'a';P_node p=lst,np=new node(lst->len+1);
        while (p&&!p->nxt[ID]) p->nxt[ID]=np,p=p->fa;
        if (!p) np->fa=ro; else
        {
            P_node q=p->nxt[ID];
            if (p->len+1==q->len) np->fa=q; else
            {
                P_node nq=new node(p->len+1);
                memcpy(nq->nxt,q->nxt,sizeof(q->nxt));
                nq->fa=q->fa;q->fa=nq;np->fa=nq;
                while (p&&p->nxt[ID]==q) p->nxt[ID]=nq,p=p->fa;
            }
        }
        lst=np;
    }
    void make_SAM(char *s) {for (int i=0; s[i]!='\0';i++) Insert(s[i]);}
    int LCS(char *s) //求此后缀自动机对应字符串与s的LCS
    {
        int ans=0,len=0;P_node p=ro;
        for (int i=0;s[i]!='\0';i++)
        {
            int ID=s[i]-'a';
            if (p->nxt[ID]) p=p->nxt[ID],len++; else
            {
                while (p&&!p->nxt[ID]) p=p->fa;
                if (!p) p=ro,len=0; else len=p->len+1,p=p->nxt[ID];
            }
            ans=max(ans,len); //从所有len中刷出最优解
        }
        return ans;
    }
};
SAM sam;
char A[N],B[N];
int main()
{
    #ifndef  ONLINE_JUDGE 
    freopen("./in.txt","r",stdin);
  #endif
    scanf("%s %s",A,B);
//  cout<<A<<endl;
//  cout<<B<<endl;
    sam.make_SAM(A);
    int ans = sam.LCS(B);
    printf("%d\n",ans);

  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}

不过还是比较喜欢写静态的?

参考了zqc大爷的代码风格:

/* ***********************************************
Author :111qqz
Created Time :2017年11月03日 星期五 18时20分42秒
File Name :2774_SAM.cpp
************************************************ */

#include <bits/stdc++.h>
#define PB push_back
#define fst first
#define sec second
#define lnxt l,m,rt<<1
#define rnxt 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;

const int maxn = 5E5;

struct node{
    node*nxt[26],*fail;
    LL len,cnt;
    int ind;
    int occ;
};
struct SAM{
    node no[maxn];
    node*root;
    int cnt;
    node*newnode(){
    return &no[cnt++];
    }
    SAM(){
    cnt = 0;
    root = newnode();
    }
    node*add(int c,node*p){
        node*cur = newnode();
        cur->len = p->len+1;
        while(p&&!p->nxt[c]){
            p->nxt[c] = cur;
            p = p->fail;
        }
        if(!p){
            cur->fail = root;
            return cur;
        }
        node*q = p->nxt[c];
        if(p->len+1==q->len){
            cur->fail = q;
        }else{
            node*nq = newnode();
            *nq = *q;
            q->fail = cur->fail = nq;
            nq->len = p->len+1;
            while(p&&p->nxt[c]==q){
                p->nxt[c] = nq;
                p = p->fail;
            }
        }
        return cur;
    }
    int LCS(string s)
    {
//  cout<<"S:"<<s<<endl;
    int ans=0,len=0;
    node *p=root;
    for ( auto i:s)
    {
        int ID = i-'a';
        //cout<<"id:"<<ID<<" s[i]:"<<i<<" i:"<<i<<endl;
        if (p->nxt[ID]) p=p->nxt[ID],len++;
        else
        {
        while (p&&!p->nxt[ID]) p=p->fail;
        if (!p) p=root,len=0;else len=p->len+1,p=p->nxt[ID];
        }
        ans = max(ans,len);
    }
    return ans;
    }
};
SAM sam;
string A,B;
int main()
{
    #ifndef  ONLINE_JUDGE 
//  freopen("./in.txt","r",stdin);
  #endif
    node *cur =sam.root;
    cin>>A>>B;
    for ( auto i:A) cur = sam.add(i-'a',cur);
    int ans = sam.LCS(B);
    printf("%d\n",ans);

  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}








/* ***********************************************
Author :111qqz
Created Time :2017年11月15日 星期三 19时06分15秒
File Name :SAM.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
const int N=5E5+7;
struct SAM
{
    struct state
    {
    int len, link, nxt[MAXALP];
    int leftmost; //某个状态的right集合中r值最小的
    int rightmost;//某个状态的right集合的r的最大值
    int Right; //right集合大小
    };
    state st[N*2];
    char S[N];
    int sz, last,rt;
    char s[N];
    int cnt[2*N],rk[2*N];//for radix sort
    void init()
    {
    sz = 0;
    last = rt = ++sz;
    st[1].len = 0;
    st[1].link=-1;
    st[1].rightmost=0;
    ms(st[1].nxt,-1);
    }
    void extend(int c,int head)
    {
    int cur = ++sz;
    st[cur].len = st[last].len + 1;
    st[cur].leftmost = st[cur].rightmost = 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;
        st[clone].rightmost = st[q].rightmost;
        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;
    }
    void pre()  //跑拓扑序,预处理一些东西
    {
    for ( int i = sz ; i >= 2 ; i--)
    {
        int v = rk[i];
        int fa = st[v].link;
        if (fa==-1) continue;
        st[fa].rightmost = max(st[fa].rightmost,st[v].rightmost);
        st[fa].Right += st[v].Right;
    }
    }
    void solve()
    {

    LL ans = 0 ;
    for ( int i = 1 ; i <= sz ; i++) if (st[i].link!=-1&&st[i].rightmost-st[i].leftmost>st[st[i].link].len)
        ans += min(st[i].len,st[i].rightmost-st[i].leftmost)-st[st[i].link].len;
    printf("%lld\n",ans);
    }
    int LCS(char *s)
    {
    int ans = 0,len = 0 ;
    int p = rt;
    for ( int i = 0 ,_len = strlen(s) ; i < _len ; i++)
    {
        int ID = s[i]-'a';
        if (st[p].nxt[ID]!=-1) p = st[p].nxt[ID],len++;
        else
        {
        while (p!=-1&&st[p].nxt[ID]==-1) p = st[p].link;
        if (p==-1) p=rt,len=0;else len = st[p].len+1,p = st[p].nxt[ID];
        }
      //  printf("len:%d\n",len);
        ans = max(ans,len);
    }
    return ans;
    }
}A;
char B[N]; 
int main()
{
#ifndef  ONLINE_JUDGE 
    freopen("./in.txt","r",stdin);
#endif
    A.init();
    cin>>A.S>>B;
    for ( int i = 0 ,len=strlen(A.S) ;  i < len ; i++) A.extend(A.S[i]-'a',i);
    int ans = A.LCS(B);
    cout<<ans<<endl;
#ifndef ONLINE_JUDGE  
    fclose(stdin);
#endif
    return 0;
}

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付