三种思路求解最长回文子串问题（字符串+DP 或字符串HASH+二分答案）

た入场券 2023-10-06 16:49 3阅读 0赞

## 三种思路求解最长回文子串问题（字符串+DP 或 字符串HASH+二分答案） ##

#### 文章目录 ####

*  三种思路求解最长回文子串问题（字符串+DP 或 字符串HASH+二分答案）
 *   *   *  问题：
         *  思路1：DP（ 时间：O（n^2）;空间：O(n ^ 2)）
         *   *  代码：
         *  思路2：中心扩展算法（ 时间：O(n^2）;空间：O(1) ）
         *   *  代码：
         *  思路3：字符串HASH+二分答案（ 时间：O(nlogn）;空间：O(n) ）
         *   *  代码：

#### 问题： ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][20210314110110742.png]

#### 思路1：DP（ 时间：O（n^2）;空间：O(n ^ 2)） ####

对于每个长度大于2的回文串，都有以下性质：去掉首尾的字符后，它还是一个回文串  
  利用上述性质可用DP解题，设DP\[i\]\[j\]表示从下标i到下标j的子串是否为回文串，输入的字符串为s，即：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70 1]

边界条件即考虑长度为1和2的回文串：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70 2]  
  需要注意填充dp数组的时候要按列的顺序填充，因为推出某个位置的dp值需要位于该位置左下方的数据，若按行填充将无法推出dp值  
  最后取DP\[i\]\[j\]=true且j-i最大的一项即可，i和j即为回文串开始和结束的下标

##### 代码： #####

class Solution {
        
    public:
        string longestPalindrome(string s) {
        
            int i;
            int j;
            int n=s.size();
            vector<vector<bool>> dp( n,vector<bool> (n) );
            for( i=0;i<dp.size();i++ )
            {
        
                dp[i][i]=true;
                if( i<dp.size()-1 )
                    dp[i][i+1]= ( s[i]==s[i+1] );
            }
            for( j=0;j<dp.size();j++ )
            {
        
                for( i=0;i<dp.size();i++ )
                {
           
                    if( i+1<=j-1 )
                        dp[i][j]= ( dp[i+1][j-1] ) && ( s[i]==s[j] ); 
                }
            }
            int index1=0;
            int index2=0;
            int maxx=1;
            for( i=0;i<dp.size();i++ )
            {
        
                for( j=i+1;j<dp.size();j++ )
                {
        
                    if( dp[i][j]==true )
                    {
        
                        if( j-i+1>=maxx )
                        {
        
                            maxx=j-i+1;
                            index1=i;
                            index2=j;
                        }
                    }
                }
            }
            string ans = s.substr( index1,index2-index1+1 );
            return ans;
        }
    };

#### 思路2：中心扩展算法（ 时间：O(n^2）;空间：O(1) ） ####

通过上述DP算法可以看出，所有的状态在转移的时候的可能性都是唯一的，即：  
![在这里插入图片描述][20210314151946723.png]  
  即从所有边界情况开始，可以推出所有的状态。边界情况即为长度为2和1的字符串，将它们看作回文串中心，对它们进行左右扩展，遍历得到所有可能的情况

##### 代码： #####

class Solution {
        
    public:
        string longestPalindrome(string s) {
        
            int index1=0;
            int index2=0;
            int i;
            int j;
            int maxx=1;
            int left;
            int right;
            int len;
            for( i=1;i<s.size();i++ )
            {
           
                left=i-1;
                right=i+1;
                len=1;
                while( left>=0 && right<s.size() && s[left]==s[right] )
                {
        
                    len+=2;
                    if( len>maxx )
                    {
        
                        maxx=len;
                        index1=left;
                        index2=right;
                    }
                    left--;
                    right++;
                }
            }
            for( i=0,left=i,j=i+1,right=j;i<s.size()-1;i++,j++ )
            {
           
                    left=i;
                    right=j;
                    len=0;
                    while( left>=0 && right<s.size() && s[left]==s[right] )
                    {
        
                        len+=2;
                        if( len>maxx )
                        {
        
                            maxx=len;
                            index1=left;
                            index2=right;
                        }
                        left--;
                        right++;
                    }
            }
            return s.substr( index1,maxx );
        }
    };

#### 思路3：字符串HASH+二分答案（ 时间：O(nlogn）;空间：O(n) ） ####

我们需要遍历回文子串的长度来寻找最长回文串，可以考虑使用二分答案进行遍历。对于回文子串的长度，我们无法使用二分答案枚举，因为回文子串的长度不具有单调性，例如aba，不存在长度为2的回文串，但存在长度为3的回文串。但我们可以转换一种思路，将回文串看成是由回文中心和回文半径组成 ，回文半径具有单调性，例如aabaa，以b为回文中心，回文半径为2的回文串为aabaa，它存在，那么回文半径为1的回文串一定存在，即为aba。因此我们可以用二分答案来枚举回文半径，在确定回文半径后，我们再枚举回文中心，判断该子串是否为回文串。  
  对于回文中心的确定，这里需要注意回文串长度的奇偶性问题。若回文串长度为奇数，则很好理解，例如aba，即为以b为回文中心，回文半径为1的回文串。若回文串长度为偶数，例如abba，回文中心在哪呢？我们可以将两个b之间的回文空隙看成是回文中心，那么该回文串便是以回文空隙为回文中心，回文半径为2的回文串。在程序中，我们可以用空隙左边点的下标表示回文空隙。判断一个串是否为回文串，即判断回文中心两边的两个串是否相反，因奇偶性不同导致回文中心选取不同，需要分奇偶两种情况讨论。在程序中，我们枚举每个回文中心，但我们此时不能判断该回文中心和回文半径确定的串长度到底是奇数还是偶数，因此我们需要把串长当成奇数判断一次，再把串长当做偶数判断一次。  
  如何判断回文中心两边的两个串是否相反？字符串HASH此时就要登场了。我们从前往后扫描字符串创建hash\[\]，再从后往前扫描字符串创建rhash\[\]（创建两个Hash数组的操作可以在一个循环中同时进行）。  
  若回文串长度为偶数，回文中心坐标为i，回文半径为k，则我们需要判断`s[i - k + 1，i + k]`是否为回文串，也即判断`s[i - k + 1, i]`与`s[i + 1, i + k]`是否相反。利用字符串HASH，上述判断等价于判断`HASH[i - k + 1,i]`与`RHASH[n - (i + k) + 1,n - (i + 1) + 1]`是否相等

--------------------

解释如下：`HASH[i - k + 1,i]`对应的是`s[i - k + 1, i]`，这很容易理解。为什么`s[i + 1, i + k]`的反序对应的是`RHASH[n - (i + k) + 1,n - (i + 1) + 1]`呢？首先，`s[i + 1, i + k]`的正序对应的是`HASH[i + 1,i + k]`，由于RHASH创建的过程是反序扫描字符串的，因此正序的第p位，对应的是反序的倒数第p位，也就是反序的正数第n - p + 1位(n表示字符串s长度)。那么正序第`i + 1`位，对应反序第`n - (i + 1) + 1`位，同理，正序第`i + k`位，对应反序第`n - (i + k) + 1`位，因此`RHASH[n - (i + k) + 1,n - (i + 1) + 1]`对应的正是`HASH[i + 1,i + k]`的颠倒，若`HASH[i - k + 1,i]`与`RHASH[n - (i + k) + 1,n - (i + 1) + 1]`相等，则`HASH[i - k + 1,i]`与`HASH[i + 1,i + k]`的颠倒相等，即回文中心两边的串相反。

--------------------

若回文串长度为奇数，我们需要判断`s[i - k,i + k]`是否为回文串，也即判断`s[i - k,i]`与`s[i,i + k]`是否相反。利用字符串HASH，上述判断等价于判断`HASH[i - k,i]`与`RHASH[n - (i + k) + 1,n - i + 1]`是否相等

**需要注意的点：**

*  二分答案枚举回文半径的下界为0，上界为s串的长度/2
 *  由于最后需要返回最长回文子串，因此我们要预设一个最长回文子串长度LL，若当前遍历到的回文串长度大于LL，将LL更新，并保存回文串的上下界，用于最后返回结果。若回文半径为k，偶数长度的回文串长为k \* 2，奇数长度的回文串长为k \*2 + 1。若该轮枚举回文中心后，LL没有被更新，则当前回文半径不满足要求，否则当前回文半径满足要求。
 *  在枚举回文中心时，注意不要越界，回文串长度为偶数时，若回文中心下标为i，回文半径为k，对应的串为`s[i - k + 1，i + k]`，需保证`i - k + 1 >= 1 && i + k <= n`。长度为奇数时同理，对应的串为`s[i - k,i + k]`，需保证`i - k >= 1 && i + k <= n`

##### 代码： #####

class Solution {
        
        static int ansL, ansR, ll;
        public String longestPalindrome(String s) {
        
            long p = 2333;
            ansL = 0;
            ansR = 0;
            ll = 0;
            int i, l = 0, r = s.length() / 2, mid, n = s.length();
            long[] hash = new long[n + 1];
            long[] rHash = new long[n + 1];
            long[] pw = new long[n + 1];
            for (i = 1;i <= n;i++) {
        
                hash[i] = hash[i - 1] * p + s.charAt(i - 1) - 'a' + 1;
                rHash[i] = rHash[i - 1] * p + s.charAt(n - i) - 'a' + 1;
            }
            for (i = 1, pw[0] = 1;i <= n;i++) {
        
                pw[i] = pw[i - 1] * p;
            }
            while(l < r) {
        
                mid = (l + r + 1) / 2;
                if (check(mid, s, hash, rHash, pw)) {
        
                    l = mid;
                } else {
        
                    r = mid - 1;
                }
            }
            return s.substring(ansL, ansR + 1);
        }
    
        static boolean check(int r, String s, long[] hash, long[] rHash, long[] pw) {
        
            int i, n = s.length(), temp = ll;
            for (i = 1;i <= n;i++) {
        
                //偶数长度
                    if (i - r + 1 >= 1 && i + r <= n && hash[i] - hash[i - r] * pw[r] == rHash[n - (i + 1) + 1] - rHash[n - (i + r)] * pw[r]) {
        
                        if (2 * r > ll) {
        
                            ansL = i - r;
                            ansR = i + r - 1;
                            ll = 2 * r;
                        }
                    }
                // 奇数长度
                    if (i - r >= 1 && i + r <= n && hash[i] - hash[i - r - 1] * pw[r + 1] == rHash[n - i + 1] - rHash[n - (i + r)] * pw[r + 1]) {
        
                        if (2 * r + 1 > ll) {
        
                            ansL = i - r - 1;
                            ansR = i + r - 1;
                            ll = 2 * r + 1;
                        }
                    }
    
            }
            return ll != temp;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210314110057954.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70
[20210314110110742.png]: https://img-blog.csdnimg.cn/20210314110110742.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210314111149718.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20210314145002297.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70
[20210314151946723.png]: https://img-blog.csdnimg.cn/20210314151946723.png