制杖四合一,HEOI以前居然出这种**题,看来HE还是联考比较好= =
首先对第二个串建SAM
第一个简单,以每个位置为起点在SAM上走,失配时更新答案
第二个先在第二个串上预处理$firs[i][j]$每个字母在位置$i$后最早在$j$出现,然后在第一个串里$n^2$枚举在$firs$上走,失配时更新答案(这是不是就是序列自动机啊=。=
第三个设个$dp[i][j]$表示考虑前$i$个状态为$j$的答案,然后和第一个一样
第四个$dp[i][j]$第二维改为表示第$j$个,然后和第二个一样
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=,M=;
char a[N],b[N];
int l1,l2,tot,lst;
int firs[N][],dp[N][M];
int fth[M],trs[M][],len[M];
void Insert(int ch)
{
int newn=++tot,nde=lst;
lst=newn,len[newn]=len[nde]+;
while(nde&&!trs[nde][ch])
trs[nde][ch]=newn,nde=fth[nde];
if(!nde)
fth[newn]=;
else
{
int tran=trs[nde][ch];
if(len[tran]==len[nde]+)
fth[newn]=tran;
else
{
int rnde=++tot; len[rnde]=len[nde]+;
for(int i=;i<=;i++) trs[rnde][i]=trs[tran][i];
fth[rnde]=fth[tran],fth[tran]=fth[newn]=rnde;
while(nde&&trs[nde][ch]==tran)
trs[nde][ch]=rnde,nde=fth[nde];
}
}
}
void Solve(int typ)
{
int ans=l1;
if(typ==)
{
for(int i=;i<=l1;i++)
{
int nde=;
for(int j=i;j<=l1;j++)
{
nde=trs[nde][(int)a[j]];
if(!nde) {ans=min(ans,j-i+); break;}
}
}
}
if(typ==)
{
for(int i=;i<=l1;i++)
for(int j=;j<=tot;j++)
dp[i][j]=l1; dp[][]=;
for(int i=;i<=l1;i++)
for(int j=;j<=tot;j++)
{
dp[i][j]=min(dp[i][j],dp[i-][j]);
int tran=trs[j][(int)a[i]];
if(!tran) ans=min(ans,dp[i-][j]+);
else dp[i][tran]=min(dp[i][tran],dp[i-][j]+);
}
}
if(typ==)
{
for(int i=;i<=;i++) firs[l2][i]=l2+;
for(int i=l2-;~i;i--)
for(int j=;j<=;j++)
firs[i][j]=(b[i+]==j)?i+:firs[i+][j];
for(int i=;i<=l1;i++)
{
int pos=;
for(int j=i;j<=l1;j++)
{
pos=firs[pos][(int)a[j]];
if(pos>l2) {ans=min(ans,j-i+); break;}
}
}
}
if(typ==)
{
for(int i=;i<=l1;i++)
for(int j=;j<=l2;j++)
dp[i][j]=l1; dp[][]=;
for(int i=;i<=l1;i++)
for(int j=;j<=l2;j++)
{
dp[i][j]=min(dp[i][j],dp[i-][j]);
int fir=firs[j][(int)a[i]];
if(fir>l2) ans=min(ans,dp[i-][j]+);
else dp[i][fir]=min(dp[i][fir],dp[i-][j]+);
}
}
printf("%d\n",ans);
}
int main()
{
scanf("%s%s",a+,b+);
l1=strlen(a+),l2=strlen(b+),tot=lst=;
for(int i=;i<=l1;i++) a[i]-='a';
for(int i=;i<=l2;i++) b[i]-='a';
for(int i=;i<=l2;i++) Insert(b[i]);
for(int i=;i<=;i++) Solve(i);
return ;
}