题目大意：给定字符串A和B，求A最短的子串/子序列S满足S不是B的子串/子序列
这题真TM有毒*2
搞法类似这道题
然后子串是后缀自动机 子序列自然就是序列自动机了= =
每更新一个x节点时所有没有x的后继的节点都连向这个节点
每个节点的parent是这个字母上一次出现的位置
每个字母记录最后一次出现的位置 更新指针时沿着parent指针撸一遍就行了
#include
#include
#include
#include
#define M 4040 using namespace std; char A[M],B[M]; struct Suffix_Automaton{ struct Sam{ Sam *son[26],*parent; int max_dpt; Sam() {} Sam(int _):max_dpt(_) {} }mempool[M],*C; Sam *root,*last; Suffix_Automaton() { C=mempool; last=root=new (C++)Sam(0); } void Extend(int x) { Sam *p=last; Sam *np=new (C++)Sam(p->max_dpt+1); for(;p&&!p->son[x];p=p->parent) p->son[x]=np; if(!p) np->parent=root; else { Sam *q=p->son[x]; if(p->max_dpt+1==q->max_dpt) np->parent=q; else { Sam *nq=new (C++)Sam(p->max_dpt+1); memcpy(nq->son,q->son,sizeof nq->son); nq->parent=q->parent; q->parent=nq;np->parent=nq; for(;p&&p->son[x]==q;p=p->parent) p->son[x]=nq; } } last=np; } }substr_A,substr_B; struct Sequence_Automaton{ struct Sqa{ Sqa *son[26],*parent; }mempool[M],*C; Sqa *root,*last[27]; Sequence_Automaton() { C=mempool; last[26]=root=new (C++)Sqa; } void Extend(int x) { Sqa *p,*np=new (C++)Sqa; int i; for(i=0;i<=26;i++) for(p=last[i];p&&!p->son[x];p=p->parent) p->son[x]=np; np->parent=last[x]; last[x]=np; } }subseq_A,subseq_B; struct abcd{ int x,y,dpt; abcd() {} abcd(int _,int __,int ___): x(_),y(__),dpt(___) {} }q[M]; int v[M][M]; int BFS1()//str-str { int i,r=0,h=0; q[++r]=abcd(0,0,0); v[0][0]=true; while(r!=h) { abcd sta=q[++h]; for(i=0;i<26;i++) { if(!substr_A.mempool[sta.x].son[i]) continue; if(!substr_B.mempool[sta.y].son[i]) return sta.dpt+1; int xx=substr_A.mempool[sta.x].son[i]-substr_A.root; int yy=substr_B.mempool[sta.y].son[i]-substr_B.root; if(v[xx][yy]==1) continue; v[xx][yy]=1; q[++r]=abcd(xx,yy,sta.dpt+1); } } return -1; } int BFS2()//str-seq { int i,r=0,h=0; q[++r]=abcd(0,0,0); v[0][0]=true; while(r!=h) { abcd sta=q[++h]; for(i=0;i<26;i++) { if(!substr_A.mempool[sta.x].son[i]) continue; if(!subseq_B.mempool[sta.y].son[i]) return sta.dpt+1; int xx=substr_A.mempool[sta.x].son[i]-substr_A.root; int yy=subseq_B.mempool[sta.y].son[i]-subseq_B.root; if(v[xx][yy]==2) continue; v[xx][yy]=2; q[++r]=abcd(xx,yy,sta.dpt+1); } } return -1; } int BFS3()//seq-str { int i,r=0,h=0; q[++r]=abcd(0,0,0); v[0][0]=true; while(r!=h) { abcd sta=q[++h]; for(i=0;i<26;i++) { if(!subseq_A.mempool[sta.x].son[i]) continue; if(!substr_B.mempool[sta.y].son[i]) return sta.dpt+1; int xx=subseq_A.mempool[sta.x].son[i]-subseq_A.root; int yy=substr_B.mempool[sta.y].son[i]-substr_B.root; if(v[xx][yy]==3) continue; v[xx][yy]=3; q[++r]=abcd(xx,yy,sta.dpt+1); } } return -1; } int BFS4()//seq-seq { int i,r=0,h=0; q[++r]=abcd(0,0,0); v[0][0]=true; while(r!=h) { abcd sta=q[++h]; for(i=0;i<26;i++) { if(!subseq_A.mempool[sta.x].son[i]) continue; if(!subseq_B.mempool[sta.y].son[i]) return sta.dpt+1; int xx=subseq_A.mempool[sta.x].son[i]-subseq_A.root; int yy=subseq_B.mempool[sta.y].son[i]-subseq_B.root; if(v[xx][yy]==4) continue; v[xx][yy]=4; q[++r]=abcd(xx,yy,sta.dpt+1); } } return -1; } int main() { //freopen("sus.in","r",stdin); //freopen("sus.out","w",stdout); int i; scanf("%s%s",A+1,B+1); for(i=1;A[i];i++) { substr_A.Extend(A[i]-'a'); subseq_A.Extend(A[i]-'a'); } for(i=1;B[i];i++) { substr_B.Extend(B[i]-'a'); subseq_B.Extend(B[i]-'a'); } cout<