最短不公共子串（后缀自动机+序列自动机+bfs）

最短不公共子串

题意：

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

思路：

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

压行思路：由于后缀自动机与序列自动机都可以看做DAG，而在 $bfs$bfs的时候也只需要用到边，因此在忽略这两种自动机的其他结构后，就变得一样啦！四个 $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);
}