浅谈回文串问题

回文串问题是字符串类型的题目中常见的一类。在绝大多数情况下，但凡涉及字符串问题都对“暴力算法”以及dfs等形式不太友好，常见的解决思路有动态规划，而除此之外，利用自动匹配机的性质，大牛们又发明了巧妙而高效的算法。本文在涉及“回文串类型问题”的解法之上，主要罗列一些常见的解决思路。

最粗暴的解法:暴力法O(N^3)

首先，可能大多数人都会想到利用回文串的性质，即S = reverse(S)，即对于一个字符串，如果将其倒置后仍然与原串相同，那么其为回文串。由此，我们可以得到这样的代码:

for(int size = 1; size <= s.size();++size ){

    for(int j = 0 ; j < s.size() - size + 1; ++j){

          string tmp(s.substr(j,size));

          reverse(tmp.begin(),tmp.end());

          isPd[j][j+size-1] = tmp == s.substr(j,size);

    }

}

尽管看上去非常通俗易懂，但是很可惜，基本上使用暴力法都无法通过所有测试用例，因为时间复杂度太高了。很自然，我们需要优化一下时间复杂度。

进阶一、通用解法:动态规划,时间复杂度O(n^2)

在之前的文章中，本人也曾提及“涉及字符串问题时，不妨先往动态规划(dynamic programming)”的方向去思考，而在处理回文串问题时，我们一样能够利用动态规划来解决。

但凡涉及回文串，无论问题的形式如何，其本质都是一样的：对于一个已知的字符串，只要我们知道其任意子串s[i][j](i为字串的起始下标，j为字串的结束下标)是否为回文串，几乎就能以此来转换为解。

现在，状态空间也很明显，我们无非需要两个维度，一个维度表示起始位置，一个维度表示结束为止，那么dp[i][j]也就表示当前状态是否对应于回文串.如果是回文串,则为true,否则为false(这里建议用vector

类型而不要使用vector

类型，因为前者实际是按位存储的，后者是按字节存储，所以前者的空间开销要小于后者)。

我们很快可以得到转移方程

dp[i][j] = dp[i+1][j-1] && s[i] == s[j]

其意义是，如果一个字符串的第一个元素与最后一个元素相同，并且除了第一个元素与最后一个元素外，剩余的字串也是回文串，那么这个字符串一定是回文串。此性质很容易推导出来，不妨在纸上动手画一画就能看出。

由此，我们可以得到这样类似的代码:

….处理长度为1和2的子串..

then

for(int size = 3; size <= s.size();++size){

     for(int j = 0; j < s.size() - size + 1;++j){

        dp[j][j+size-1] = dp[j+1][j+size – 2] && s[j] == s[j+size-1];

    }

}

结束后,通过保存下来的数组dp,我们也就可以知道字符串的任意字串是否为回文串了。

进阶二、中心扩散(Manacher)，马拉车算法:时间复杂度O(n)

实际上，在本人第一次接触到Manacher时，不由为其精妙的理念与效率而折服。作为解决字符串问题的算法，其时间复杂度竟然能够降低到线性级别，实在与当时自己的认知有所不同—-毕竟从直觉来看，很难想象回文串问题能够以线性时间遍历所有状态空间。

本算法的精妙之处在于：利用回文串的对称性。

简单来说，概括如下：

1、假设对于一个回文串，以及其中心位置，由回文串的性质可知，从其中心向两侧逐步扩散到边界为止，每一步所对应范围的字串都是回文串。

2、此外，如果我们已知一个回文串的中心点与其边界范围。那么，在大多数情况下，位于边界内且关于此中心点对称的两点a、b，如果有回文串以a为中心，那么以b为中心的回文串与以a为中心的回文串完全相同，或者说，具有完全一致的“状态与空间大小”。

现在，利用性质1、2实际上我们就可以遍历该字符串所对应的所有回文串的状态空间了。这里以奇数长度的回文串为例:

比如现在有一个字符串ababcbabca，我们知道，任意一个单独的字符都是“回文”。并且回文半径为1(这里的半径指的是从中心开始，到边界为止的长度，显然，对于一个字符来说，中心点是自己，边界也是自己，长度为1).

让我们从字符串的起始位置开始遍历，可以看到，直到第三个字符(a)为止，已出现的以某个位置为中心的回文串一共只有两个，分别是a和b，且半径均为1.而在便利到第三个字符时，出现了转机：

让我们以第三个字符为中心，开始向外扩散。首先扩散到left = 2，right = 4，对应的字符均为b，显然，bab是一个回文串。这里运用了朴素的匹配方法，大致代码如下:

int left = i,right = i;

while(left > 0 && right < s.size() && s[left] = s[right]){

          d[i]++;

}

d[i]表示以i为中心的，范围最大的回文串的半径，如果我们确定了d[i]的值，也就意味着子串[i – d[i],……i+d[i]]内的所有以i为中心的子串也都是回文串。

延续前述的思路，让我们继续遍历中心点i,每当我们遍历到位置i时，已经计算完了i之前的所有状态空间d[0]….d[i-1]。此外。我们还记录了上一个状态空间的边界[left,right].

现在，i分为两种情况:

(1)i处于上一个范围最大的状态空间的边界外，也就是说，此时i > right.那么很不幸，我们没有办法利用回文串的性质来推演了，只能老老实实用朴素算法进行中心扩散，求解出当前的状态空间d[i]

(2)如果当前i位于上一个范围最大的状态空间的边界内，也就是说，i <= right，那么由于回文串的对称性，我们可以得到d[i] = d[left + right - i]---大多树情况下是这样，但如果d[left + right - i]的半径，超过了right - i怎么办？对于超过边界的字串，我们显然无法再继续利用对称性来求解了，只能先固定d[i]的值，让其最大为right - i,然后老老实实用朴素匹配法进行扩散。

最终，我们可以得到类似下述的代码:

vector

d(n);

for(int i = 0 , left = 0 , right = -1 ; i < s.size();++i ){

     int r =  i > right ? 1 : min(d[left + r – i] , r – i);

     while( i – r  >= 0 && i + r < n && s[i - r] ==  s[i + r] ){

         r++;

    }

   if( i + r > right){

        right = i + r;

        left = i – r;    

}

}

通过上述代码，我们就遍历了从i = 0开始一直到 i = s.size() – 1为止的所有中心点的状态。

到这里，已经基本阐述完了Manacher的思想，但也许还有一些问题没有解决？

如果回文串是偶数长度怎么办？它的中心点在哪？

为了解决奇数长度和偶数长度回文串中心点不对应的问题，这里，我们需要借助一种巧妙的策略—-“插入辅助字符”。

比如对于一个回文串abba,我们可以在头尾以及每个字符的间隙中插入符号”#”,这样，它就变成了#a#b#b#a#，显然，经过扩展后，偶数长度的回文串也扩展为了奇数长度，而奇数长度的回文串比如aba，扩展后为#a#b#a#依然为奇数长，这样，就巧妙地将两类情况归一化了。

现在，我们只需要遍历除了头尾之外的，扩展字串的每一个位置，进行中心扩散，即可遍历回文串的所有状态空间了:

1、如果当前位置符号为“#”,那么其对应于原字串中偶数长度回文串的中心

2、如果当前位置符号为正常字母，那么其对应于原字串中奇数长度的回文串中心

另外，我们可以归纳出以下规律：

1、如果当前中心是”#”,经过中心扩散，其得到的半径长r = 原半径长*2 + 1;所以真正对应的原状态的半径为 (r – 1)/2;

2、如果当前中心是字母，经过中心扩散，其得到的半径长r = 原半径长 * 2,所以真正对应的原状态的半径为r/2;

通过这样的映射，我们就遍历完原问题的所有状态空间了！

总结

求解回文串问题，考虑优化时间复杂度的话，大多情况下我们需要利用到回文串的对称性质。比如前述的动态规划，其实运用到了回文串的性质1，而Manacher算法则进一步运用了回文串的中心对称性。实际上，即时跳出字符串问题，很多时候，如果我们能够归纳出当前问题的一些基本性质并加以应用，往往都可以巧妙地规避“冗余计算”，实现时空复杂度的优化！