第一、二问：
就是最小的最长公共长度+1，设f[i][j]为a匹配到i，b匹配到j，第一问的转移是f[i][j]=(a[i]==b[j]?f[i-1][j-1]+1:0)，第二问的转移是f[i][j]=(a[i]==b[j]?f[i-1][j-1]+1:f[i][j-1])，注意这里更新最小公共长度的时候，如果f[i][j]==i就不能更新，因为不能从前面随便新加的字符，后面加的不能保证不相等 第三问： 对b串建SAM，设g[i]为匹配到SAM上点i时的最短长度，然后枚举a的字符，如果能转移就转移，否则用失配位置更新答案 第四问： 同上，不用SAM，设c[i][j]为b串位置i后面第一个字符j的位置，当成SAM的ch转移，然后dp同上#include#include #include using namespace std;const int N=4005;int n,m,f[N][N],ans,ch[N][26],fa[N],tot=1,cur=1,la,dis[N],g[N],l[26],c[N][26];char a[N],b[N];void ins(int c,int id){ la=cur; dis[cur=++tot]=id; int p=la; for(;p&&!ch[p][c];p=fa[p]) ch[p][c]=cur; if(!p) fa[cur]=1; else { int q=ch[p][c]; if(dis[q]==dis[p]+1) fa[cur]=q; else { int nq=++tot; dis[nq]=dis[p]+1; memcpy(ch[nq],ch[q],sizeof(ch[q])); fa[nq]=fa[q]; fa[q]=fa[cur]=nq; for(;ch[p][c]==q;p=fa[p]) ch[p][c]=nq; } }}int main(){ scanf("%s%s",a+1,b+1); n=strlen(a+1),m=strlen(b+1); ans=1e9; for(int i=1;i<=n;i++) { int mx=0; for(int j=1;j<=m;j++) { if(a[i]==b[j]) f[i][j]=f[i-1][j-1]+1; mx=max(mx,f[i][j]); } if(mx!=i) ans=min(ans,mx+1); } printf("%d\n",ans>n?-1:ans); ans=1e9; memset(f,0,sizeof(f)); for(int i=1;i<=n;i++) { int mx=0; for(int j=1;j<=m;j++) { if(a[i]==b[j]) f[i][j]=f[i-1][j-1]+1; else f[i][j]=f[i][j-1]; mx=max(mx,f[i][j]); } if(mx!=i) ans=min(ans,mx+1); } printf("%d\n",ans>n?-1:ans); for(int i=1;i<=m;i++) ins(b[i]-'a',i); ans=1e9; memset(g,0x3f,sizeof(g)); g[1]=0; for(int i=1;i<=n;i++) for(int j=1;j<=tot;j++) { if(!ch[j][a[i]-'a']) ans=min(ans,g[j]+1); else g[ch[j][a[i]-'a']]=min(g[ch[j][a[i]-'a']],g[j]+1); } printf("%d\n",ans>n?-1:ans); for(int i=m;i>=0;i--) { for(int j=0;j<26;j++) c[i][j]=l[j]; l[b[i]-'a']=i; } ans=1e9; memset(g,0x3f,sizeof(g)); g[0]=0; for(int i=1;i<=n;i++) for(int j=m;j>=0;j--) { if(!c[j][a[i]-'a']) ans=min(ans,g[j]+1); else g[c[j][a[i]-'a']]=min(g[c[j][a[i]-'a']],g[j]+1); } printf("%d\n",ans>n?-1:ans); return 0;}