原题链接

题解

1.把字符串倒过来，记作 \(S_1\) 其最大公共子串是回文串，所以这部分可以不用求，字符串长度减去最大公共子串的长度就是答案
2.怎么求最大公共子串的长度呢？
假设我们已经知道字符串a和字符串b及其所有子串的lbs，此时往字符串b末尾添加一个字符c变成字符串b1，而字符串a中以最后一个字符c的前一个字符为最后一个位置的子串a1，则lbs(b1,a)=max(lbs(a1,b)+1,lbs(a,b))

code

#include<bits/stdc++.h>
using namespace std;
int dp[1005]={0};
int main()
{
    string s1,s2;//字符串型有很多强大的处理方法
    cin>>s1;
    int len=s1.length();
    for(int i=len-1;i>=0;i--)
    {
        s2.push_back(s1[i]);
    }

    for(int i=0;i<len;i++)
    {
        for(int j=len-1;j>=1;j--)
        {
            if(s2[j]==s1[i]) dp[j]=max(dp[j-1]+1,dp[j]);//由i-1和j-1  i-1和j 继承而来
        }
        if(s2[0]==s1[i]) dp[0]=1;
        for(int j=1;j<len;j++) dp[j]=max(dp[j],dp[j-1]);//由i和j-1继承而来
    }

    cout<<len-dp[len-1];
    return 0;
}