制杖四合一，HEOI以前居然出这种**题，看来HE还是联考比较好= =
首先对第二个串建SAM
第一个简单，以每个位置为起点在SAM上走，失配时更新答案
第二个先在第二个串上预处理$firs[i][j]$每个字母在位置$i$后最早在$j$出现，然后在第一个串里$n^2$枚举在$firs$上走，失配时更新答案(这是不是就是序列自动机啊=。=
第三个设个$dp[i][j]$表示考虑前$i$个状态为$j$的答案，然后和第一个一样
第四个$dp[i][j]$第二维改为表示第$j$个，然后和第二个一样
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int N=2005,M=4005; 6 char a[N],b[N]; 7 int l1,l2,tot,lst; 8 int firs[N][26],dp[N][M]; 9 int fth[M],trs[M][26],len[M]; 10 void Insert(int ch) 11 { 12 int newn=++tot,nde=lst; 13 lst=newn,len[newn]=len[nde]+1; 14 while(nde&&!trs[nde][ch]) 15 trs[nde][ch]=newn,nde=fth[nde]; 16 if(!nde) 17 fth[newn]=1; 18 else 19 { 20 int tran=trs[nde][ch]; 21 if(len[tran]==len[nde]+1) 22 fth[newn]=tran; 23 else 24 { 25 int rnde=++tot; len[rnde]=len[nde]+1; 26 for(int i=0;i<=25;i++) trs[rnde][i]=trs[tran][i]; 27 fth[rnde]=fth[tran],fth[tran]=fth[newn]=rnde; 28 while(nde&&trs[nde][ch]==tran) 29 trs[nde][ch]=rnde,nde=fth[nde]; 30 } 31 } 32 } 33 void Solve(int typ) 34 { 35 int ans=l1; 36 if(typ==1) 37 { 38 for(int i=1;i<=l1;i++) 39 { 40 int nde=1; 41 for(int j=i;j<=l1;j++) 42 { 43 nde=trs[nde][(int)a[j]]; 44 if(!nde) {ans=min(ans,j-i+1); break;} 45 } 46 } 47 } 48 if(typ==3) 49 { 50 for(int i=0;i<=l1;i++) 51 for(int j=0;j<=tot;j++) 52 dp[i][j]=l1; dp[0][1]=0; 53 for(int i=1;i<=l1;i++) 54 for(int j=1;j<=tot;j++) 55 { 56 dp[i][j]=min(dp[i][j],dp[i-1][j]); 57 int tran=trs[j][(int)a[i]]; 58 if(!tran) ans=min(ans,dp[i-1][j]+1); 59 else dp[i][tran]=min(dp[i][tran],dp[i-1][j]+1); 60 } 61 } 62 if(typ==2) 63 { 64 for(int i=0;i<=25;i++) firs[l2][i]=l2+1; 65 for(int i=l2-1;~i;i--) 66 for(int j=0;j<=25;j++) 67 firs[i][j]=(b[i+1]==j)?i+1:firs[i+1][j]; 68 for(int i=1;i<=l1;i++) 69 { 70 int pos=0; 71 for(int j=i;j<=l1;j++) 72 { 73 pos=firs[pos][(int)a[j]]; 74 if(pos>l2) {ans=min(ans,j-i+1); break;} 75 } 76 } 77 } 78 if(typ==4) 79 { 80 for(int i=0;i<=l1;i++) 81 for(int j=0;j<=l2;j++) 82 dp[i][j]=l1; dp[0][0]=0; 83 for(int i=1;i<=l1;i++) 84 for(int j=0;j<=l2;j++) 85 { 86 dp[i][j]=min(dp[i][j],dp[i-1][j]); 87 int fir=firs[j][(int)a[i]]; 88 if(fir>l2) ans=min(ans,dp[i-1][j]+1); 89 else dp[i][fir]=min(dp[i][fir],dp[i-1][j]+1); 90 } 91 } 92 printf("%d ",ans); 93 } 94 int main() 95 { 96 scanf("%s%s",a+1,b+1); 97 l1=strlen(a+1),l2=strlen(b+1),tot=lst=1; 98 for(int i=1;i<=l1;i++) a[i]-='a'; 99 for(int i=1;i<=l2;i++) b[i]-='a'; 100 for(int i=1;i<=l2;i++) Insert(b[i]); 101 for(int i=1;i<=4;i++) Solve(i); 102 return 0; 103 }