题目描述
在虐各种最长公共子串、子序列的题虐的不耐烦了之后，你决定反其道而行之。
一个串的“子串”指的是它的连续的一段，例如bcd是abcdef的子串，但bde不是。
一个串的“子序列”指的是它的可以不连续的一段，例如bde是abcdef的子串，但bdd不是。
下面，给两个小写字母串A，B，请你计算：
(1) A的一个最短的子串，它不是B的子串
(2) A的一个最短的子串，它不是B的子序列
(3) A的一个最短的子序列，它不是B的子串
(4) A的一个最短的子序列，它不是B的子序列
输入输出格式
输入格式：
有两行，每行一个小写字母组成的字符串，分别代表A和B。
输出格式：
输出4行，每行一个整数，表示以上4个问题的答案的长度。如果没有符合要求的答案，输出-1.
输入输出样例
输入样例#1：
aabbccabcabc
输出样例#1：
2424
输入样例#2：
aabbccaabbcc
输出样例#2：
-1-12-1
说明
对于20%的数据，A和B的长度都不超过20
对于50%的数据，A和B的长度都不超过500
对于100%的数据，A和B的长度都不超过2000
题解
这题好烦……
据说还有大佬是用dp的方法做的……相当于做了四道题……先膜为敬……
然后看到有大佬是直接建上后缀自动机和回文自动机，然后在上面跑BFS，如果跑不动了就返回答案，可以保证最优
然后我因为一堆sb错误调了一个多小时……
为啥取队头元素不能直接整个结构体取啊！为啥我SAM都能打错啊！
1 //minamoto 2 #include3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 9 char buf[1<<21],*p1=buf,*p2=buf; 10 char sr[1<<21],z[20];int C=-1,Z; 11 inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;} 12 inline void print(int x){ 13 if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x; 14 while(z[++Z]=x%10+48,x/=10); 15 while(sr[++C]=z[Z],--Z);sr[++C]='\n'; 16 } 17 const int N=4005; 18 struct SAM{ 19 int fa[N],ch[N][26],l[N];int last,cnt; 20 SAM(){last=cnt=1;} 21 void ins(int c){ 22 int p=last,np=++cnt;last=np,l[np]=l[p]+1; 23 for(;p&&!ch[p][c];p=fa[p]) ch[p][c]=np; 24 if(!p) fa[np]=1; 25 else{ 26 int q=ch[p][c]; 27 if(l[q]==l[p]+1) fa[np]=q; 28 else{ 29 int nq=++cnt;l[nq]=l[p]+1; 30 memcpy(ch[nq],ch[q],sizeof(ch[q])); 31 fa[nq]=fa[q],fa[q]=fa[np]=nq; 32 for(;ch[p][c]==q;p=fa[p]) ch[p][c]=nq; 33 } 34 } 35 } 36 }SA,SB; 37 struct SqAM{ 38 int ch[N][26],lst[26],fa[N]; 39 int root,cnt; 40 SqAM(){root=cnt=1;for(int i=0;i<26;++i) lst[i]=1;} 41 void ins(int c){ 42 int p=lst[c],np=++cnt; 43 fa[np]=p; 44 for(int i=0;i<26;++i) 45 for(int j=lst[i];j&&!ch[j][c];j=fa[j]) 46 ch[j][c]=np; 47 lst[c]=np; 48 } 49 }SQA,SQB; 50 struct node{ 51 int a,b,step; 52 node(int a=0,int b=0,int step=0):a(a),b(b),step(step){} 53 }; 54 int vis[N][N]; 55 int bfs1(){ 56 queue q; 57 q.push(node(1,1,0)); 58 vis[1][1]=1; 59 while(!q.empty()){ 60 int ra=q.front().a,rb=q.front().b,st=q.front().step; 61 for(int i=0;i<26;i++){ 62 int va=SA.ch[ra][i],vb=SB.ch[rb][i]; 63 if(va&&vb){ 64 if(vis[va][vb]==1) continue; 65 q.push(node(va,vb,st+1)); 66 vis[va][vb]=1; 67 } 68 if(va&&!vb) return st+1; 69 } 70 q.pop(); 71 } 72 return -1; 73 } 74 int bfs2(){ 75 queue q; 76 q.push(node(1,1,0)); 77 vis[1][1]=2; 78 while(!q.empty()){ 79 int ra=q.front().a,rb=q.front().b,st=q.front().step; 80 for(int i=0;i<26;i++){ 81 int va=SA.ch[ra][i],vb=SQB.ch[rb][i]; 82 if(va&&vb){ 83 if(vis[va][vb]==2) continue; 84 q.push(node(va,vb,st+1)); 85 vis[va][vb]=2; 86 } 87 if(va&&!vb) return st+1; 88 } 89 q.pop(); 90 } 91 return -1; 92 } 93 int bfs3(){ 94 queue q; 95 q.push(node(1,1,0)); 96 vis[1][1]=3; 97 while(!q.empty()){ 98 int ra=q.front().a,rb=q.front().b,st=q.front().step; 99 for(int i=0;i<26;i++){100 int va=SQA.ch[ra][i],vb=SB.ch[rb][i];101 if(va&&vb){102 if(vis[va][vb]==3) continue;103 q.push(node(va,vb,st+1));104 vis[va][vb]=3;105 }106 if(va&&!vb) return st+1;107 }108 q.pop();109 }110 return -1;111 }112 int bfs4(){113 queue q;114 q.push(node(1,1,0));115 vis[1][1]=4;116 while(!q.empty()){117 int ra=q.front().a,rb=q.front().b,st=q.front().step;118 for(int i=0;i<26;i++){119 int va=SQA.ch[ra][i],vb=SQB.ch[rb][i];120 if(va&&vb){121 if(vis[va][vb]==4) continue;122 q.push(node(va,vb,st+1));123 vis[va][vb]=4;124 }125 if(va&&!vb) return st+1;126 }127 q.pop();128 }129 return -1;130 }131 char a[N],b[N];int tot1,tot2;char ch;132 int main(){133 scanf("%s%s",a+1,b+1);134 tot1=strlen(a+1),tot2=strlen(b+1);135 for(int i=1;i<=tot1;++i) SA.ins(a[i]-'a'),SQA.ins(a[i]-'a');136 for(int i=1;i<=tot2;++i) SB.ins(b[i]-'a'),SQB.ins(b[i]-'a');137 printf("%d\n%d\n%d\n%d\n",bfs1(),bfs2(),bfs3(),bfs4());138 return 0;139 }