自动搬运

查看原文

来自洛谷，原作者为

	UniverseofHK Day day up!

搬运于2025-08-24 21:56:37，当前版本为作者最后更新于2019-10-22 19:57:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

楼上巨佬的思路都很清晰！但代码略显冗长

题意：

问最短的满足：是A的子串（子序列），且不是B的子串（子序列，子序列（子串））。（共四个问题）

思路：

1. 子串问题，考虑后缀自动机；子序列问题，考虑序列自动机；
2. 然后本题要求属于前者，而不属于后者的子结构，可以考虑暴力的在两种DAG上同时跑；若前者可以跑，后者却不能跑，说明此子结构仅属于前者，好像问题就解决了？
3. 但仔细一想，长度为$2000$的串子序列似乎太多了，好像不能跑完？这里我们考虑$bfs$，记录哪些状态（二维）已经遍历；对于已经遍历过的状态，虽然此前在遍历时当前状态所代表的子结构可能不一样（比如序列自动机通过不同的路径到达某个节点），但此后节点的可到达性却只与当前节点是否可到达有关，而与怎样到达的无关，故后续节点是否可到达在之前的$bfs$中已经处理好了；因此可以像普通的$bfs$一样，遍历过的状态可接忽略掉！（使用$n×n$的$vis$记录）
4. 复杂度：后缀自动机为$O(n*∑)$；序列自动机为$O(n*∑)$；每个后缀自动机节点数为$2*n$，每个序列自动机节点数为$n$，$bfs$遍历时每个点遍历边数为$∑$，因此$bfs$复杂度为$O(n*∑)$;
5. 总复杂度为$O(n*∑)$。（$∑$为字符集大小）

压行思路：由于后缀自动机与序列自动机都可以看做DAG，而在$bfs$的时候也只需要用到边，因此在忽略这两种自动机的其他结构后，就变得一样啦！四个$bfs$完全可以写在一起。

代码

#include "bits/stdc++.h"
using namespace std;

const int maxn = 4e3+10;

struct P{ int a, b, c; };
int ch[2][2][maxn][26], fa[2][maxn], len[2][maxn];
bool vis[maxn][maxn];
int tot[2]={1,1}, last[2]={1,1};
char s[maxn];

void add(int c, int f) {
    int p=last[f], np=last[f]=++tot[f];
    len[f][np]=len[f][p]+1;
    for(; p&&!ch[f][1][p][c]; p=fa[f][p]) ch[f][1][p][c]=np;
    if(!p) fa[f][np]=1;
    else {
        int q=ch[f][1][p][c];
        if(len[f][q]==len[f][p]+1) fa[f][np]=q;
        else {
            int nq=++tot[f]; len[f][nq]=len[f][p]+1;
            fa[f][nq]=fa[f][q]; fa[f][q]=fa[f][np]=nq;
            memcpy(ch[f][1][nq],ch[f][1][q],104);
            for(; p&&ch[f][1][p][c]==q; p=fa[f][p]) ch[f][1][p][c]=nq;
        }
    }
}

void pre(int f) {
    for(int i=strlen(s+1); i; --i) {
        memcpy(ch[f][0][i-1],ch[f][0][i],104);
        ch[f][0][i-1][s[i]-'a']=i;
    }
}

void bfs(int f1, int f2) {
    memset(vis,0,sizeof(vis));
    queue<P> q;
    q.push((P){f1,f2,0}); vis[f1][f2]=1;
    while(!q.empty()) {
        P now=q.front(); q.pop();
        for(int i=0; i<26; ++i) if(ch[0][f1][now.a][i]) {
            if(ch[1][f2][now.b][i]) {
                int a=ch[0][f1][now.a][i], b=ch[1][f2][now.b][i];
                if(!vis[a][b]) vis[a][b]=1, q.push((P){a,b,now.c+1});
            }
            else return (void)printf("%d\n", now.c+1);
        }
    }
    printf("-1\n");
}

int main() {
    scanf("%s", s+1);
    pre(0); for(int i=1; s[i]; ++i) add(s[i]-'a',0);
    scanf("%s", s+1);
    pre(1); for(int i=1; s[i]; ++i) add(s[i]-'a',1);
    bfs(1,1); bfs(1,0); bfs(0,1); bfs(0,0);
}

更棒的观赏体验！