回文相关

LeetCode

最长回文系列

最长回文子串
最长回文子序列

解题思路：
1. dp，两种思路，一种是仅dp bool，另外一种是dp具体的值
2. 枚举中心节点，暴力生成所有的
3. Manacher's Algorithm

// 子序列
int longestPalindrome(string s) {
    int n = s.size();
    for (int i = 0; i < n; ++i) dp[i][i] = 1;
    for (int i = 0; i < n - 1; ++i) dp[i][i+1] = s[i] == s[i+1]?2:1;
    for (int i = n - 1; i >= 0; --i) {
        for (int j = i + 2; j < n; ++j) { // j > i
            if (s[i] == s[j]) dp[i][j] = dp[i+1][j-1]+2;
            else dp[i][j] = max(dp[i][j-1], dp[i+1][j]);
        }
    }
    return dp[0][n-1]; //注意这里只有一个字符串
}

// 子串 
for (size_t i = 0; i < s.size(); i++) {
    f[i][i] = true;
    for(size_t j=0; j<i; j++){ //[j,i]
        f[j][i] = (s[j] == s[i] && (i - j < 2 || f[j + 1][i - 1])); 
        if (f[j][i] && max_len < (i - j + 1)) {
            max_len = i - j + 1;
            start = j; 
        }
    }
}

// 中心扩展模板
class Solution {
    public int countSubstrings(String S) {
        int N = S.length(), ans = 0;
        for (int center = 0; center < 2*N-1; ++center) {
            int left = center / 2;
            int right = left + center % 2;
            while (left >= 0 && right < N && S.charAt(left) == S.charAt(right)) {
                ans++;
                left--;
                right++;
            }
        }
        return ans;
    }
}

统计回文的次数

允许重复
1. https://leetcode.com/problems/count-different-palindromic-subsequences/discuss/272297/DP-C%2B%2B-Clear-solution-explained
2. 中心扩展的思路，应该更简单

不允许重复
https://www.cnblogs.com/grandyang/p/7942040.html

其他的扩展

也基本上都要利用前边的解法去生成辅助信息等。

回文分割1
回文分割2

1. Palindrome Pairs
   暴力枚举、判断的方式过不了OJ，要想办法从一个字符串出发，想办法把另外一半给拼接出来