题解 P4112 【[HEOI2015]最短不公共子串】
UniverseofHK · · 题解
楼上巨佬的思路都很清晰！但代码略显冗长
题意：
问最短的满足：是A的子串（子序列），且不是B的子串（子序列，子序列（子串））。（共四个问题）
思路：
- 子串问题，考虑后缀自动机；子序列问题，考虑序列自动机；
- 然后本题要求属于前者，而不属于后者的子结构，可以考虑暴力的在两种DAG上同时跑；若前者可以跑，后者却不能跑，说明此子结构仅属于前者，好像问题就解决了？
- 但仔细一想，长度为
2000 的串子序列似乎太多了，好像不能跑完？这里我们考虑bfs ，记录哪些状态（二维）已经遍历；对于已经遍历过的状态，虽然此前在遍历时当前状态所代表的子结构可能不一样（比如序列自动机通过不同的路径到达某个节点），但此后节点的可到达性却只与当前节点是否可到达有关，而与怎样到达的无关，故后续节点是否可到达在之前的bfs 中已经处理好了；因此可以像普通的bfs 一样，遍历过的状态可接忽略掉！（使用n×n 的vis 记录） - 复杂度：后缀自动机为
O(n*∑) ；序列自动机为O(n*∑) ；每个后缀自动机节点数为2*n ，每个序列自动机节点数为n ，bfs 遍历时每个点遍历边数为∑ ，因此bfs 复杂度为O(n*∑) ; - *总复杂度为$O(n∑)
**。（ ∑$为字符集大小）
压行思路：由于后缀自动机与序列自动机都可以看做DAG，而在
代码
#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);
}