SSL1813回文词-白红宇的个人博客

SSL1813回文词

发布日期：2021-05-07 09:38:35 浏览次数：20 分类：精选文章

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

要解决给定字符串变成回文所需插入的最小字符数的问题，可以采用动态规划的方法计算最大公共子序列（MPS），然后根据公式计算每个中心点的最小插入数。

步骤说明：

初始化MPS表：创建一个二维数组 o，其中 o[i][j] 表示前 i 个字符和后 j 个字符的最大公共子序列长度。

填充MPS表：使用双重循环计算每个 o[i][j]，如果当前字符相等则递归加1，否则取左右两边的最大值。

计算每个中心点的插入数：对于每个中心点 i，计算对应的 o[i][n-i-1]，然后代入公式 f[i] = n - 1 - 2 * o[i][n-i-1]。

找出最小插入数：遍历所有中心点，找出最小的 f[i]，即为所需的最小插入数。

代码实现：

#include 
   
    #include 
    
     #include 
     
      #include 
      #include 
       
        using namespace std;void computeMPS(const string &s, string &y) {    int n = s.size();    o = new int[n+1][n+1];    for (int i = 0; i <= n; ++i) {        for (int j = 0; j <= n; ++j) {            if (i == 0 || j == 0) {                o[i][j] = 0;            } else if (s[i-1] == y[j-1]) {                o[i][j] = o[i-1][j-1] + 1;            } else {                o[i][j] = max(o[i-1][j], o[i][j-1]);            }        }    }}int main() {    int n;    string z;    cin >> n >> z;    string y = z;    reverse(y.begin(), y.end());    computeMPS(z, y);        int mn = n - o[n][n];        for (int i = 0; i < n; ++i) {        int j = n - i - 1;        if (j < 0) break;        int current = n - 1 - 2 * o[i][j];        if (current < mn) mn = current;    }        cout << mn << endl;        delete[] o;    return 0;}

解释：

MPS表初始化：o 是一个二维数组，用于存储前 i 个字符和后 j 个字符的最大公共子序列长度。

填充MPS表：通过双重循环遍历字符串，计算每个位置的 o[i][j]，如果字符匹配则递归计算，否则取最大值。

计算插入数：对于每个中心点 i，计算其对应的 o[i][n-i-1]，代入公式得到需要插入的字符数 f[i]。

遍历找出最小值：遍历所有中心点，找到最小的插入数 mn，输出即为答案。

该方法通过动态规划有效地计算了最小插入数，适用于长度较大的字符串，确保了时间复杂度在合理范围内。

上一篇：P1854 花店橱窗布置&&SSLOJ1626

下一篇：P1026 统计单词个数&&SSL1017

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

步骤说明：

代码实现：

解释：

发表评论

最新留言

关于作者

推荐文章