数据结构：LDP最大回文子串

Bertha 。 2022-05-31 12:54 160阅读 0赞

# 最长回文子串 #

这是一个很经典的DP动态规划问题

# 代码如下 #

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    #include <iomanip>
    
    using namespace std;
    
    
    static const string a = "abASDFGGFDSAfgdba";
    static const int lena = a.length();
    
    int ByDPLPS()
    {
        int** cal = new int*[lena];
        for (int i = 0; i<lena; i++)
            cal[i] = new int[lena];
    
        for (int i = 0; i<lena; i++)
            for (int j = 0; j<lena; j++)
                cal[i][j] = (i == j) ? 1 : 0;
        int maxLen = 1, x = 0, y = 0;
    
        //其实思路和最大公共子序列是一样的,不一样的是下面循环的设计
        //cal[i][j]表示从i到j的子序列是否是回文字符串
        //cal[i][j]=cal[i+1][j-1]+2;  表明i是一来后面的元素i+1,所以i要倒序
        //j是依赖前面的元素,所以要顺序遍历
        for (int i = lena - 1; i >= 0; i--)
        {
            for (int j = i + 1; j<lena; j++)
            {
                if (a[i] == a[j])
                    cal[i][j] = cal[i + 1][j - 1] + 2;
                else
                    cal[i][j] = 0;
    
                if (cal[i][j]>maxLen)
                {
                    maxLen = cal[i][j];
                    x = i;
                    y = j;
                }
            }
        }
    
        char* res = new char[maxLen + 1];
        res[maxLen] = '\0';
        int k = maxLen - 1;
        int i = y;
    
        while (k >= 0)
        {
            res[k--] = a[i--];
        }
        cout << maxLen << "    ==   " << (y - x + 1) << endl;
        cout << "LPS is following:" << endl << res << endl;
        for (int i = 0; i<lena; i++)
            delete[] cal[i];
        delete[] cal, res;
        return maxLen;
    }
    
    
    int main()
    {
        int len = ByDPLPS();
        cout << "LPS: " << len << endl;
        system("pause");
    }