回文字符串问题

什么是回文字符串？
「正向和反向观察得到的字符串顺序是相同的」 或者 「关于中心对称的字符串」
比如字符串：abcba 和 abccba，都是回文串

常用的判断回文子串相关的两种方法：「中心扩展」和「动态规划1」
判断回文子序列的方法一般是「动态规划2」

此外还有一种在线性时间内求解最长回文子串的算法：Manacher 算法

中心扩展法

基于回文字符串对称性的特点，我们可以采取从中心向两边扩展的方法，得到回文子串，回文中心分为两种情况，以单个字母为中心 和 以两个字母为中心：
1）以单个字母为回文中心

2）以两个字母为回文中心

假设字符串长度为$len$，则回文中心一共有 $2\times len-1$ 个，分别是 $len$ 个单字符和 $len-1$ 个双字符。
总结：「中心扩展法」的思想就是遍历以一个字符或两个字符为中心可得到的回文子串。中心拓展法适用于连续子串是否是回文串的判断，不太适用于不连续子序列是否是回文串的判断。
连续子序列一般用第二类动态规划方法，状态量$dp[i][j]$为字符串在$[i,j]$区间的回文序列个数（int 类型）。

第一类动态规划法

由于长字符串会依赖短字符串的回文串，所以我们可以采用动态规划来实现。

这里需要二维的 $dp[][]$ 数组，设置状态量：$dp[i][j]$ 表示字符串 $s$ 在$[i,j]$区间的子串是否是一个回文串。
当我们判断 $[i..j]$ 是否为回文子串时，只需要判断 $s[i]==s[j]$，同时判断 $[i-\mathrm{1..}j-1]$ 是否为回文子串即可
需要注意有两种特殊情况：$[i,i]$ or $[i,i+1]$，即：子串长度为 1 或者 2。所以需要加一个条件限定 $j-i<2$
状态转移方程如下：

dp[i][j] = (s[i] == s[j]) && (j - i < 2 || dp[i + 1][j - 1])

解释：当 $s[i]==s[j]\&\&(j-i<2||dp[i+1][j-1])$ 时，$dp[i][j]=true$，否则为$false$

Manacher （马拉车）算法

复杂度为 O(n) 的Manacher 算法是在线性时间内求解最长回文子串的算法。也可以用于求解回文串的个数。

Manacher 的基本原理：
定义一个新概念臂长，表示中心扩展算法向外扩展的长度。如果一个位置的最大回文字符串长度为 2 * length + 1 ，其臂长为 length。

Manacher 算法也会面临奇数长度和偶数长度的问题，它的处理方式是在所有的相邻字符中间插入 $\#$，比如 $abaa$ 会被处理成 $\#a\#b\#a\#a\#$，这样可以保证所有找到的回文串都是奇数长度的，以任意一个字符为回文中心，既可以包含原来的奇数长度的情况，也可以包含原来偶数长度的情况。假设原字符串为 S，经过这个处理之后的字符串为 s。

我们用 f(i) 来表示以 s 的第 i 位为回文中心，可以拓展出的最大回文半径，那么 f(i) - 1 就是以 i 为中心的最大回文串长度 。
（后续内容详见超链接，此方法只做了解）

回文子串问题

回文子串问题一般用中心拓展与第一类动态规划方法求解。
可以用这道题的题解当模板，进行理解学习：
647. 回文子串
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：
输入：s = “abc”
输出：3
解释：三个回文子串: “a”, “b”, “c”

示例 2：
输入：s = “aaa”
输出：6
解释：6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”

法一：中心拓展法
「中心扩展法」的思想就是遍历以一个字符或两个字符为中心可得到的回文子串，分两种情况调用isPalindromic(string s, int i, int j)函数。

//法一：中心扩展法
 	int ans = 0;
    int countSubstrings(string s) {
        int n = s.size();
        for(int i = 0; i < n; ++i){
        	// 以单个字母为中心的情况
            isPalindromic(s, i, i);
            // 以两个字母为中心的情况
            isPalindromic(s, i, i + 1);
        }
        return ans;
    }
    void isPalindromic(string s, int i, int j){
        while(i >= 0 && j < s.size()){
            if(s[i] != s[j]) return;
                ++ans;
                ++j;
                --i;
        }
    }

中心拓展法的另一种解法：
长度为 $n$ 的字符串会生成 $2n-1$ 组回文中心 $[l_i,r_i]$，其中 $l_i=i/2$，$r_i=l_i+(i\%2)$ 。这样我们只要从 $0$ 到 $2n-2$ 遍历 $i$，就可以得到所有可能的回文中心，这样就把奇数长度和偶数长度两种情况统一起来了。

	int countSubstrings(string s) {
        int n = s.size();
        int num = 0;
        for(int i = 0; i < 2 * n - 1; ++i){
            int l = i / 2;
            int r = l + ( i % 2);
            while(l >= 0 && r < n && s[l] == s[r]){
                ++num;
                --l;
                ++r;
            }
        }       
        return num;
    }

法二：动态规划
由于长字符串会依赖短字符串的回文串数量，所以我们可以采用动态规划来实现。
$dp[i][j]$ 表示字符串$s$在$[i,j]$区间的子串是否是一个回文串，当 $s[i]==s[j]$时，如果$dp[i][j]$是回文串，则要么$[i,j]$区间仅有一个或两个字符，要么 $dp[i+1][j-1]$ 是一个回文串

	//法二：动态规划  
	//dp[i][j] 表示字符串s在[i,j]区间的子串是否是一个回文
	//当 s[i]==s[j] 时，要么[i, j]区间仅有一个或两个字符，要么看 dp[i+1][j-1] 是不是一个回文串    
    int countSubstrings(string s) {
        int n = s.size();
        int ans = 0;
        //n行n列，其实只用到下三角
        vector<vector<bool>> dp(n, vector<bool>(n));
        for(int j = 0; j < n; ++j){
            for(int i = 0; i <= j; ++i){
                if(s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1])){
                    dp[i][j] = true;
                    ++ans;
                }
            }
        }
        return ans;
    }

用下面这道题加深对上面模板的套用和理解。
5. 最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：
输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。

法一：中心扩展法
还是沿用了上一题的模板，唯一的改动就是记录一下最长子串的起始点和长度。

	//法一：中心扩展法
	int maxi = 0, maxlen = 0;
    string longestPalindrome(string s) {
        int n = s.size();
        for(int i = 0; i < n; ++i){
            ispalindromic(s, i, i);
            ispalindromic(s, i, i + 1);
        }
        return s.substr(maxi, maxlen);
    }
    void ispalindromic(string& s, int i, int j){
        while(i >= 0 && j < s.size()){
            if(s[i] != s[j]) return;
            if(j - i + 1 > maxlen){
                maxi = i;
                maxlen = j - i + 1;
            }
            --i;
            ++j;
        }
    }

法二：动态规划
由于长字符串会依赖短字符串的回文串长度，所以我们可以采用动态规划来实现。
沿用了上一题的模板，唯一的改动就是记录一下最长子串的起始点和长度。
$dp[i][j]$ 表示字符串$s$在$[i,j]$区间的子串是否是一个回文串，当 $s[i]==s[j]$时，如果$dp[i][j]$是回文串，则要么$[i,j]$区间仅有一个或两个字符，要么 $dp[i+1][j-1]$ 是一个回文串

	//法二：动态规划
	string longestPalindrome(string s) {
        int maxi = 0,  maxlen = 0;
        int n = s.size();
        vector<vector<
						

							上一篇：							
								利用堆栈解密回音字符串的 Aha 算法							
						
						

							下一篇：							
								确定回声字符串、回声列表和回声计数（python 实现）