$dp$。

$dp[i][j]$表示$s[i]$到$s[j]$和$t[lent-1+i-j]$到$t[lent-1]$有$dp[i][j]$位相同，然后枚举一遍$dp[i][j]$就可以算出答案了。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int maxn=5100;char s[maxn],t[maxn];int lens,lent;int dp[maxn][maxn];int main(){ memset(s,0,sizeof s); memset(t,0,sizeof t); scanf("%s%s",s,t); lens=strlen(s), lent=strlen(t); for(int i=lens;i
           
            =lens) continue; if(j==i) { if(s[i]==t[lent-1]) dp[i][j]=1; else dp[i][j]=0; ans=min(ans,j-i+1-dp[i][j]+lent-(j-i+1)); } else { dp[i][j]=dp[i+1][j]; if(s[i]==t[lent-1+i-j]) dp[i][j]++; ans=min(ans,j-i+1-dp[i][j]+lent-(j-i+1)); } } } printf("%d\n",ans); return 0;}