构造回文

逃离我推掉我的手 2023-01-20 09:43 185阅读 0赞

## 构造回文 ##

提到回文串，自然要利用回文串的特点，想到将源字符串逆转后，“回文串”（不一定连续）相当于顺序没变  
求原字符串和其反串的最大公共子序列（不是子串，因为可以不连续）的长度（使用动态规划很容易求得），然后用原字符串的长度减去这个最大公共子串的长度就得到了最小编辑长度。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dYX3RpbWk_size_16_color_FFFFFF_t_70]

#include <iostream>
    #include <string>
    #include <algorithm>
    
    using namespace std;
    
    const int MAX = 1001;
    int MaxLen[MAX][MAX];   //最长公共子序列，动态规划求解
    
    int maxLen(string s1, string s2)
    {
        
        int length1 = s1.size();
        int length2 = s2.size();
        for (int i=0; i<length1; ++i)
        {
        
            MaxLen[i][0] = 0;
        }
        for (int j=0; j<length2; ++j)
        {
        
            MaxLen[0][j] = 0;
        }
    
        for (int i=1; i<=length1; ++i)
        {
        
            for (int j=1; j<=length2; ++j)
            {
        
                if (s1[i-1] == s2[j-1])
                {
        
                    MaxLen[i][j] = MaxLen[i-1][j-1] +1;
                }
                else
                {
        
                    MaxLen[i][j] = max(MaxLen[i-1][j], MaxLen[i][j-1]);
                }
            }
        }
    
        return MaxLen[length1][length2];
    }
    
    
    int main()
    {
        
        string s;
        while (cin>>s) {
        
            int length = s.size();
            if (length == 1)
            {
        
                cout<<1<<endl;
                continue;
            }
            //回文串特点
            string s2 = s;
            reverse(s2.begin(), s2.end());
            int max_length = maxLen(s, s2);
            cout<<length - max_length<<endl;
        }
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dYX3RpbWk_size_16_color_FFFFFF_t_70]: /images/20221021/0f059abd6e5d4bcabca986a018fd3364.png