SPOJ 1812 LCS2 - Longest Common Substring II (后缀自动机、状压DP)

手动博客搬家: 本文发表于20181217 23:54:35, 原地址https://blog.csdn.net/suncongbo/article/details/85058680

人生第一道后缀自动机。

说实话SAM我还没学多么明白。

但是题还是要做的。

说起来这玩意真的很妙。可惜我智商低理解不了。

再次验证了代码能力菜到没边。hyw 30min写完我写2.5h.

题目链接 (洛谷)

https://www.luogu.org/problemnew/show/SP1812

题目大意

给\(n\)个长度为\(l_i\)的小写字母字符串，求它们的最长公共子串 (要求每个字符串都要出现。) \(n\le 10, l_i\le 10^5\)

题解

做法一二分+hash判断。\(O(L\log L\times n)\), 据说会TLE.

做法二后缀数组。不会。

做法三后缀自动机。

用后缀自动机的有两种做法

做法一

首先考虑如何求两个串\(A,B\)的\(LCS\). 对\(A\)串建出后缀自动机，用\(B\)串在上面匹配。

匹配时从头到尾枚举\(B\)的每一个字符，记录当前\(A\)串后缀自动机的位置\(pos\)以及当前长度\(len\), 初始\(pos=rtn, len=0\) (\(rtn\)为根节点)

当前存在一条匹配边。即son[pos][str[i]]!=0, 则\(pos\)跳到\(son[pos][str[i]]\), \(len\)增加1即可。
当前不存在一条匹配边。即son[pos][str[i]]==0, 则\(pos\)从\(u\)开始向上跳，直到pos==0或者son[pos][str[i]]==0.分别对应第3和1种情况。此时\(len\)应置为\(Len[pos]\), \(Len[u]\)表示\(u\)状态表示的最长字符串。
如果u==0表明我们匹配到了自动机外面，则此时应重置\(pos=rtn,len=0\)

这样我们可以处理\(n=2\)的情形。\(n>2\)?

对于\(A_2, A_3,...,A_n\)分别跑一次，每一个节点记录一下匹配大小的最小值，然后求最大即可。每个点记录的最小值是因为要求这个子串同时是这\(n\)个串的公共部分，求最大是对于合法的状态求出最大值。

做完了。？

少了一步

观察到\(n=2\)时\(A\)若长度较长的子串可以匹配，那么长度较短的子串也可以匹配。因此我们需要每做完一个串进行一遍更新:

if(fa[u]) mx[fa[u]] = max(mx[fa[u]],mx[u]);

做完了吗？

我们发现实际上对每个点还有限制，就是\(mx[u]\le len[u]\).

if(fa[u]) {mx[fa[u]] = max(mx[fa[u]],min(mx[u],len[fa[u]]));}

真·做完了。

代码

//Wrong Coding:

//pos = fa[pos]; curl = len[pos]; Wrong Order

//insertstr() len[np]=len[p]+1 Forgot

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#define llong long long

using namespace std;

const int N = 2e5;

const int M = 3e5;

const int S = 26;

int son[N+3][S+3];

int fa[N+3];

int len[N+3];

char a[N+3];

char b[N+3];

int buc[N+3];

int oid[N+3];

int ans[N+3];

int mx[N+3];

int sz[N+3];

int lpos,siz,rtn,lena;

void insertstr(char ch)

{

    int p = lpos,np; siz++; np = lpos = siz; sz[np] = 1; len[np] = len[p]+1;

    for(; p && son[p][ch]==0; p=fa[p]) son[p][ch] = np;

    if(p==0) {fa[np] = rtn;}

    else

    {

        int q = son[p][ch];

        if(len[p]+1==len[q]) {fa[np] = q;}

        else

        {

            siz++; int nq = siz; len[nq] = len[p]+1;

            memcpy(son[nq],son[q],sizeof(son[q]));

            fa[nq] = fa[q]; fa[np] = fa[q] = nq;

            for(; p!=0 && son[p][ch]==q; p=fa[p]) son[p][ch] = nq;

        }

    }

}

void prework()

{

    for(int i=1; i<=siz; i++) buc[len[i]]++;

    for(int i=1; i<=lena; i++) buc[i] += buc[i-1];

    for(int i=siz; i>=1; i--) oid[buc[len[i]]--] = i;

    for(int i=siz; i>=1; i--)

    {

        int pos = oid[i];

        sz[fa[pos]] += sz[pos];

    }

}

void dfs(char str[],int lens)

{

    int curl = 0,pos = rtn;

    for(int i=1; i<=lens; i++)

    {

        while(pos && son[pos][str[i]-96]==0) {pos = fa[pos]; curl = len[pos];}

        if(pos) {curl++; pos = son[pos][str[i]-96]; mx[pos] = max(mx[pos],curl);}

        else {pos = rtn; curl = 0;}

    }

    for(int i=siz; i>=1; i--)

    {

        int u = oid[i];

        if(fa[u]) {mx[fa[u]] = max(mx[fa[u]],min(mx[u],len[fa[u]]));}

        ans[u] = min(ans[u],mx[u]);

        mx[u] = 0;

    }

}

int main()

{

    memset(ans,1,sizeof(ans));

    siz = 1; rtn = 1; lpos = 1;

    scanf("%s",a+1);

    lena = strlen(a+1);

    for(int i=1; i<=lena; i++) insertstr(a[i]-96);

    prework();

    while(scanf("%s",b+1)!=EOF)

    {

        int lenb = strlen(b+1);

        dfs(b,lenb);

    }

    int fans = 0;

    for(int i=1; i<=siz; i++) {if(ans[i]<=5e6) fans = max(fans,ans[i]);}

    printf("%d\n",fans);

    return 0;

}

完了？没有呢，还有做法二。

做法二

我们考虑这个题的一个加强版：每次给\(n\)个串的一个子集，询问这个子集内的串的\(LCS\). \(n\le 20, L\le 10^5, q\le 10^5\)

做法：\(n\)个串并起来建立广义\(SAM\). 然后每个状态记录一个\(n\)位二进制数。对于第\(i\)个串先在其所到达状态标记\(2^i\). 最后把标记沿着Parent树从下往上更新一下，然后统计出每一个子集的答案，然后再用每个集合的答案更新它的子集的答案（注意避免\(O(3^n)\)会\(TLE\)）即可。

时间复杂度\(O(2^nn+nL)\)

可以参考GDOI2017微信这道题。见DC巨佬的博客：https://www.cnblogs.com/dcdcbigbig/p/10135665.html (引用已经过博主同意orz)

巴特西

SPOJ 1812 LCS2 - Longest Common Substring II (后缀自动机、状压DP)

最新文章

热门文章