Longest palindrome substring (dynamic programming)

  Longest text substring ：
    State Design ：dp[i][j] Express str[i] To str[j] Whether the string of is a palindrome substring , Is expressed as 1, It doesn't mean 0;
    State transition equation ：dp[i][j]=dp[i-1][j-1](str[i]==str[j])
                          = 0 (str[i]!=str[j]); However, attention should be paid here ,dp The value of is based on the substring length of the string (1...len) For incremental enumeration ,  Instead of subscribing with characters i As base point ,j=i+k(k=1...len), Because I'm counting the later dp[i][j] when , Need to put dp[i-1][j-1] Calculate the value of , However, at this time dp[i-1][j-1] when = It has not been calculated yet ,( A brain patch , You can figure out this logic ）;
    The border ：dp[i][i]=1, dp[i][i+1]=1(str[i]==str[i+1]);

/**
     Longest text substring ：
     State Design ：dp[i][j] Express str[i] To str[j] Whether the string of is a palindrome substring , Is expressed as 1, It doesn't mean 0;
     State transition equation ：dp[i][j]=dp[i-1][j-1](str[i]==str[j])
                          = 0 (str[i]!=str[j]);
                   However, attention should be paid here ,dp The value of is based on the substring length of the string (1...len) For incremental enumeration ,
                   Instead of subscribing with characters i As base point ,j=i+k(k=1...len), Because I'm counting the later dp[i][j] when ,
                   Need to put dp[i-1][j-1] Calculate the value of , However, at this time dp[i-1][j-1] when = It has not been calculated yet 
                  ( A brain patch , You can figure out this logic ）;
     The border ：dp[i][i]=1, dp[i][i+1]=1(str[i]==str[i+1]);
*/

/**
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int main()
{
    string str;
    cin >>str;
    int len=str.size();
    int dp[len][len]={0},ans=1;
    memset(*dp,0,sizeof dp);
    for(int i=0;i<len;++i)
    {
        dp[i][i]=1;
        if(i<len-1&&str[i]==str[i+1])
        {
            dp[i][i+1]=1;
            ans=2;
        }
    }
    for(int l=3;l<len;++l)
    {
        for(int i=0,j=0;i+l-1<len;++i)
        {
            j=i+l-1;
            if(str[i]==str[j]&&dp[i+1][j-1]==1)
            {
                dp[i][j]=1;
                ans=l;
            }
        }
    }
    cout << ans << endl;
    return 0;
}
*/

However , We can also put dp[i][j] Change the status of , So that we can output the content of the longest palindrome substring .
    State Design ：dp[i][j] Express str[i] To str[j] Whether the string of is a palindrome substring , If so, this value is the length of the palindrome substring ,
    It doesn't mean 0;
    State transition equation ：dp[i][j]=dp[i-1][j-1]+2 (str[i]==str[j])
                          = 0 (str[i]!=str[j]);
                  However, attention should be paid here ,dp The value of is based on the substring length of the string (1...len) For incremental enumeration ,
                  Instead of subscribing with characters i As base point ,j=i+k(k=1...len), Because I'm counting the later dp[i][j] when ,
                  Need to put dp[i-1][j-1] Calculate the value of , However, at this time dp[i-1][j-1] when = It has not been calculated yet
                  ( A brain patch , You can figure out this logic ）;

    The border ：dp[i][i]=1, dp[i][i+1]=2(str[i]==str[i+1]);

/**
     However , We can also put dp[i][j] Change the status of , So that we can output the content of the longest palindrome substring .
     State Design ：dp[i][j] Express str[i] To str[j] Whether the string of is a palindrome substring , If so, this value is the length of the palindrome substring ,
     It doesn't mean 0;
     State transition equation ：dp[i][j]=dp[i-1][j-1]+2 (str[i]==str[j])
                          = 0 (str[i]!=str[j]);
                   However, attention should be paid here ,dp The value of is based on the substring length of the string (1...len) For incremental enumeration ,
                   Instead of subscribing with characters i As base point ,j=i+k(k=1...len), Because I'm counting the later dp[i][j] when ,
                   Need to put dp[i-1][j-1] Calculate the value of , However, at this time dp[i-1][j-1] when = It has not been calculated yet 
                  ( A brain patch , You can figure out this logic ）;
     The border ：dp[i][i]=1, dp[i][i+1]=2(str[i]==str[i+1]);
*/

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    string str;
    cin >>str;
    int len=str.size();
    int dp[len][len]={0},ans=1;
    memset(dp,0,sizeof(dp));
    for(int i=0;i<len;++i)
    {
        dp[i][i]=1;
        if(i<len-1&&str[i]==str[i+1])
        {
            dp[i][i+1]=2;
            ans=2;
        }
    }
    for(int l=3;l<=len;++l)
    {
        for(int i=0,j=0;i+l-1<len;++i)
        {
            j=i+l-1;
            if(str[i]==str[j]&&dp[i+1][j-1]!=0)
            {
                dp[i][j]=dp[i+1][j-1]+2;
                ans=l;
            }
        }
    }
    int l=0,r=0,imax=0;
    for(int i=0;i<len;++i)
        for(int j=0;j<len;++j)
        {
            if(dp[i][j]>imax)
            {
                imax=dp[i][j];
                l=i;
                r=j;
            }
        }
    cout << ans << endl;
    cout <<imax << endl;
    for(;l<=r;++l)
        cout << str[l];
    return 0;
}

The more efficient one should be binary plus string hash How to do it , This is finished , I'll review the string again when I have time tomorrow hash, It's a little fuzzy .

When writing this code , I found a funny thing ：

That is, when the array is not a global variable ：
            If the array size is a variable , Then the array is initialized to 0 when , The value of the element may not be 0;
            If the array size is constant , Then the array is initialized to 0 when , The value of the element is 0;

/**
     When the array is not a global variable ：
             If the array size is a variable , Then the array is initialized to 0 when , The value of the element may not be 0;
             If the array size is constant , Then the array is initialized to 0 when , The value of the element is 0;
*/

/**
#include <iostream>
using namespace std;
const int maxn=10;
int main()
{
    cout << " Array size is a variable :\n";
    cout << " Enter two values :\n";
    int n, m;
    cin >> n >> m;
    int temp[n][m]={0};
    for(int i=0;i<n;++i)
        for(int j=0;j<m;++j)
            cout << temp[i][j] << ' ';
    cout << "\n The array size is const  Constant of type ：\n";
    int matr[maxn][maxn]={0};
    for(int i=0;i<maxn;++i)
        for(int j=0;j<maxn;++j)
            cout << matr[i][j] << ' ';
    cout << "\n The array size is  common  Constant :\n";
    int a[10][10]={0};
    for(int i=0;i<10;++i)
        for(int j=0;j<10;++j)
        cout << a[i][j] << ' ';
}
*/

  Here is the result of this program ：