最长回文子串与最长回文子序列(dp,Manacher),合并回文子串

最长回文子序列

#include <bits/stdc++.h>

using namespace std;

const int N = 1010, INF = 0x3f3f3f3f;

int dp[N][N], n;
string str;

void longest_palindromic_substring_dp(){
    n = str.length();
    memset(dp, 0, sizeof dp);
    for(int i = n - 1;i >= 0; i--){
        dp[i][i] = 1;
        for(int j = i + 1;j < n; j++){
            if(str[i] == str[j])dp[i][j] = dp[i + 1][j - 1] + 2;
            else dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
            cout << str.substr(i, j - i + 1) << " " << dp[i][j] << endl;
        }
    }
    cout << dp[0][n - 1];
}

int main(){
//    freopen("1.txt", "r", stdin);
    getline(cin, str);
    longest_palindromic_substring_dp();
}

最长回文子串

#include <bits/stdc++.h>

using namespace std;

int main(){
    string str;
    getline(cin ,str);
    int n = str.length();
    int dp[n][n];
    memset(dp, 0, sizeof dp);
    for (int i = 0; i < n; ++i) {
        dp[i][i] = 1;
        if(i > 0)dp[i][i - 1] = 1;
    }
    int maxv = -0x3f3f3f3f;
    for(int l = 2;l <= n; l++)
        for(int i = 0, j; (j = i + l - 1) < n; i++){
            if(str[i] == str[j] && dp[i + 1][j - 1]){
                dp[i][j] = 1;
                maxv = max(maxv, l);
            }
        }
    cout << maxv << endl;
}

最长回文子串-Manacher

#include <bits/stdc++.h>

using namespace std;

int manacher(const string& str){
    int n = str.length() * 2 + 1, maxv = 0;
    char arr[n];
    int p[n];
    for(int i = 0;i < str.length();i++){
        arr[2 * i] = '$';
        arr[2 * i + 1] = str[i];
    }
    arr[n - 1] = '$';
    int R = -1, C = -1;
    for (int i = 0; i < n; ++i) {
        p[i] = R > i ? min(R - i, p[2 * C - i]) : 1;
        while(i + p[i] < n && i - p[i] >= 0){
            if(arr[i + p[i]] == arr[i - p[i]])p[i]++;
            else break;
        }
        if(i + p[i] > R){
            R = i + p[i];
            C = i;
        }
        maxv = max(maxv, p[i]);
    }
    return maxv - 1;
}

int main(){
//    freopen("1.txt", "r", stdin);
    string line;
    getline(cin, line);
    cout << manacher(line) << endl;
}

输入两个字符串A和B，合并成一个串C，属于A和B的字符在C中顺序保持不变。如"abc"和"xyz"可以被组合成"axbycz"或"abxcyz"等。
我们定义字符串的价值为其最长回文子串的长度（回文串表示从正反两边看完全一致的字符串，如"aba"和"xyyx"）。
需要求出所有可能的C中价值最大的字符串，输出这个最大价值即可
链接：https://ac.nowcoder.com/acm/problem/13230
来源：牛客网

#include <bits/stdc++.h>

using namespace std;
const int N = 110;
int dp[N][N][N][N];
int main(){
    int tt;
    string a, b;
    cin >> tt;
    while(tt--){
        cin >> a >> b;
        int n = a.length(), m = b.length();
        a = " " + a;
        b = " " + b;
        int maxv = -0x3f3f3f3f;
        for(int len1 = 0;len1 <= n; len1++)
            for(int len2 = 0;len2 <= m; len2++)
                for(int i = 1;i + len1 -1 <=n;i++)
                    for(int k = 1;k + len2 - 1 <= m; k++)
                    {
                        int j = i + len1 - 1, l = k + len2 - 1;
                        if(len1 + len2 <= 1)dp[i][j][k][l] = 1;
                        else{
                            dp[i][j][k][l] = 0;
                            if(len1>1) dp[i][j][k][l] |= (dp[i+1][j-1][k][l] && (a[i]==a[j]));
                            if(len1 && len2) dp[i][j][k][l] |= (dp[i+1][j][k][l-1] && (a[i]==b[l]));
                            if(len1 && len2) dp[i][j][k][l] |= (dp[i][j-1][k+1][l] && (a[j]==b[k]));
                            if(len2>1) dp[i][j][k][l] |= (dp[i][j][k+1][l-1] && (b[k]==b[l]));
                        }
                        if(dp[i][j][k][l]){
                            maxv = max(maxv, len1 + len2);
                        }
                    }
        cout << maxv << endl;
    }

}