[HEOI2015]最短不公共子串

四合一的题。

简单粗暴的方法：

子串匹配——SAM

子序列匹配——序列自动机

关于序列自动机：序列自动机—— [FJOI2016]所有公共子序列问题

（其实这个玩意没有什么，n+1个点，每个点的字符集的每条出边连向其后的第一个字符，这样保证尽可能用靠前的，后面的能凑出的子序列就能更多，1号点是rt）

类似于SAM，序列自动机的路径条数就是子序列个数。

这样的话，对AB两个串各建造一个SAM和序列自动机

四问就分别在两个机子上bfs跑

如果A有的出边，而B没有，那么返回深度作为答案。

否则A，B都有，入队。

正确性：bfs按深度，会把深度为d的所有公共的子串/子序列搜完后再搜下一个。第一个合法的就是最短的。

复杂度：记忆化一下，因为到了同样一个数对(Ax,By)时候，后面的路径都是固定的了。之前没有找到过，后面也不会找到。直接continue

这样，复杂度就是状态数O(n^2)

就是考察对自动机"路径与子串一一对应"的理解。

#include<bits/stdc++.h>

#define il inline

#define reg register int

#define numb (ch^'0')

using namespace std;

typedef long long ll;

il void rd(int &x){

    char ch;bool fl=false;

    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);

    for(x=numb;isdigit(ch=getchar());x=x*+numb);

    (fl==true)&&(x=-x);

}

namespace Miracle{

const int N=;

char a[N],b[N];

int l1,l2;

struct SAM{

    int nd,cnt,fa[*N],ch[*N][];

    int len[*N];

    SAM(){

        nd=cnt=;

    }

    void ins(int c,int pos){

        //cout<<c<<" "<<pos<<" "<<cnt<<endl;

        int p=nd;nd=++cnt;

        len[nd]=pos;

        for(;p&&ch[p][c]==;p=fa[p]) ch[p][c]=nd;

        if(p==) {fa[nd]=;return;}

        int q=ch[p][c];

        if(len[q]==len[p]+){fa[nd]=q;return;}

        len[++cnt]=len[p]+;

        for(reg i=;i<=;++i) ch[cnt][i]=ch[q][i];

        fa[cnt]=fa[q];fa[q]=cnt;fa[nd]=cnt;

        for(;p&&ch[p][c]==q;p=fa[p]) ch[p][c]=cnt;

    }

}SA,SB;

struct XU{

    int cnt,ch[N][];

    int las[];

    void build(char *s,int len){

        for(reg i=len;i>=;--i){

            for(reg j=;j<=;++j){

                if(las[j]) {

                    ch[i+][j]=las[j];

                    //cout<<" to "<<i+1<<" "<<j<<" "<<las[j]<<endl;

                }

            }

            if(i)las[s[i]-'a']=i+;

        }

    }

}XA,XB;

struct po{

    int x,y,d;

    po(){}

    po(int xx,int yy,int dd){

        x=xx,y=yy,d=dd;

    }

};

queue<po>q;

int vis[*N][*N];

int bfs1(){

    while(!q.empty()) q.pop();

    q.push(po(,,));

    vis[][]=;

    while(!q.empty()){

        po now=q.front();q.pop();

        for(reg i=;i<=;++i){

            if(vis[SA.ch[now.x][i]][SB.ch[now.y][i]]==) continue;

            vis[SA.ch[now.x][i]][SB.ch[now.y][i]]=;

            if(SA.ch[now.x][i]&&!SB.ch[now.y][i]) return now.d+;

            if(SA.ch[now.x][i])

            {

                q.push(po(SA.ch[now.x][i],SB.ch[now.y][i],now.d+));

            }

        }

    }

    return -;

}

int bfs2(){

    while(!q.empty()) q.pop();

    q.push(po(,,));

    vis[][]=;

    while(!q.empty()){

        po now=q.front();q.pop();

        for(reg i=;i<=;++i){

            if(vis[SA.ch[now.x][i]][XB.ch[now.y][i]]==) continue;

            vis[SA.ch[now.x][i]][XB.ch[now.y][i]]=;

            if(SA.ch[now.x][i]&&!XB.ch[now.y][i]) return now.d+;

            if(SA.ch[now.x][i])

            {

                q.push(po(SA.ch[now.x][i],XB.ch[now.y][i],now.d+));

            }

        }

    }

    return -;

}

int bfs3(){

    while(!q.empty()) q.pop();

    q.push(po(,,));

    vis[][]=;

    while(!q.empty()){

        po now=q.front();q.pop();

        for(reg i=;i<=;++i){

            if(vis[XA.ch[now.x][i]][SB.ch[now.y][i]]==) continue;

            vis[XA.ch[now.x][i]][SB.ch[now.y][i]]=;

            if(XA.ch[now.x][i]&&!SB.ch[now.y][i]) return now.d+;

            if(XA.ch[now.x][i])

            {

                q.push(po(XA.ch[now.x][i],SB.ch[now.y][i],now.d+));

            }

        }

    }

    return -;

}

int bfs4(){

    while(!q.empty()) q.pop();

    q.push(po(,,));

    vis[][]=;

    while(!q.empty()){

        po now=q.front();q.pop();

        //cout<<now.x<<" || "<<now.y<<" dd "<<now.d<<endl;

        for(reg i=;i<=;++i){

            if(vis[XA.ch[now.x][i]][XB.ch[now.y][i]]==) continue;

            vis[XA.ch[now.x][i]][XB.ch[now.y][i]]=;

            if(XA.ch[now.x][i]&&!XB.ch[now.y][i]) return now.d+;

            if(XA.ch[now.x][i])

            {

                //cout<<" goto "<<XA.ch[now.x][i]<<" "<<

                q.push(po(XA.ch[now.x][i],XB.ch[now.y][i],now.d+));

            }

        }

    }

    return -;

}

int main(){

    scanf("%s",a+);

    scanf("%s",b+);

    l1=strlen(a+);l2=strlen(b+);

    for(reg i=;i<=l1;++i) SA.ins(a[i]-'a',i);

    for(reg i=;i<=l2;++i) SB.ins(b[i]-'a',i);

    //cout<<SA.cnt<<" "<<SB.cnt<<endl;

    XA.build(a,l1);XB.build(b,l2);

    printf("%d\n%d\n%d\n%d",bfs1(),bfs2(),bfs3(),bfs4());

    return ;

}

}

signed main(){

    Miracle::main();

    return ;

}

/*

   Author: *Miracle*

   Date: 2018/12/12 9:10:40

*/

考虑到，我们要最小化一个串的长度，使得这个串在B的机子上跑完回到NULL节点。

所以，也可以DP做。f[i][j]表示，考虑A中前i个位置，匹配到B的机子上的j位置，最小长度。直接在所有机子位置后尝试匹配i+1位，取min即可完成转移。

答案就是f[lenA][NULL]

巴特西

[HEOI2015]最短不公共子串

最新文章

热门文章