题目大意：给定字符串A和B，求A最短的子串/子序列S满足S不是B的子串/子序列 这题真TM有毒*2 搞法类似这道题 然后子串是后缀自动机 子序列自然就是序列自动机了= = 每更新一个x节点时所有没有x的后继的节点都连向这个节点 每个节点的parent是这个字母上一次出现的位置 每个字母记录最后一次出现的位置 更新指针时沿着parent指针撸一遍就行了
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<<BFS1()<<endl;cout<<BFS2()<<endl;cout<<BFS3()<<endl;cout<<BFS4()<<endl;return 0;}
，今天不想走，明天就要跑了。
