本文共 733 字，大约阅读时间需要 2 分钟。

题解：用一个字符串的逆串与原串求最大公共字串的长度 用字符串的长度 - 最大公共字串的长度就是答案

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;int dp[1005][1005];int main(){    int n;    char str1[1005],str2[1005];    scanf("%d",&n);    getchar();    while(n--)    {        scanf("%s",str1);        int l = strlen(str1);        memset(dp,0,sizeof(dp));        for(int i = 0;i < l;i++) str2[i] = str1[l-i-1];        for(int i = 0;i < l;i++)        {            for(int j = 0;j <= l;j++)            {                if(str1[i] == str2[j])                    dp[i+1][j+1] = dp[i][j] + 1;                else                    dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j]);            }        }        printf("%d\n",l - dp[l][l]);    }}
      
     
    
   

转载地址：http://mfsgi.baihongyu.com/