浅谈Manacher算法与扩展KMP之间的联系

首先,在谈到Manacher算法之前,我们先来看一个小问题:给定一个字符串S,求该字符串的最长回文子串的长度.对于该问题的求解。网上解法颇多。时间复杂度也不尽同样,这里列述几种常见的解法.

解法一

      通过枚举S的子串。然后推断该子串是否为回文。因为S的子串个数大约为

latex=\dpi{100}&space;\fn_jvn&space;N^2">浅谈Manacher算法与扩展KMP之间的联系

\dpi{100}&space;\fn_jvn&space;N^2" title="N^2" alt="">

。加上每次推断须要

latex=\dpi{100}&space;\fn_jvn&space;O(n)">浅谈Manacher算法与扩展KMP之间的联系

的时间,所以总的时间复杂度为浅谈Manacher算法与扩展KMP之间的联系,空间复杂度为浅谈Manacher算法与扩展KMP之间的联系

\dpi{100}&space;\fn_jvn&space;O(1)" title="O(1)" alt="">

.
bool check(string &S, int left, int right)
{
while (left < right && S[left] == S[right])
++left, --right;
return left >= right;
}
int solution(string &S)
{
int ans = 0;
for (int i = 0; i < S.size(); ++i)
for (int j = i; j < S.size(); ++j)
if (check(S, i, j))
ans = max(ans, j - i + 1);
return ans;
}

解法二

        我们也能够利用动态规划求解该问题。

现如果得知S[i....j]是S的一个回文子串,那么,我们相同能够得到S[i+1.....j-1]也是S的一个回文字串,换句话说,我们能够通过已知的状态求解出未知状态。现定义dp[i][j]表示S以i为起点,j为终点的子串是否为回文,状态转移方程也非常easy想到:

因为状态存在

latex=\dpi{100}&space;\fn_jvn&space;N^2">浅谈Manacher算法与扩展KMP之间的联系

种,所以时间复杂度为

latex=\dpi{100}&space;\fn_jvn&space;O(N^2)">浅谈Manacher算法与扩展KMP之间的联系

。利用滚动数组,我们能够将空间复杂度降为浅谈Manacher算法与扩展KMP之间的联系.
int solution(string &S)
{
vector<vector<bool> > dp(2, vector<bool>(S.size(), false));
int ans = 0;
for (int i = S.size() - 1; i >= 0; --i)
{
for (int j = i; j < S.size(); ++j)
{
dp[i & 1][j] = i <= j - 2 ? (S[i] == S[j] && dp[(i + 1) & 1][j - 1]) : S[i] == S[j];
if (dp[i & 1][j])
ans = max(ans, j - i + 1);
}
}
return ans;
}

解法三

         该解法是基于解法一的一种优化。在解法一中,check函数对于以i为起点,j为终点的回文子串,须要推断(j - i + 1) / 2次,但这里面也存在着某个子串不是回文,但也须要推断(j - i + 1) / 2次的情况,比方:aaabaa,aaaabcaaa....为了避免出现这样的情况,我们能够去枚举回文子串的中点。然后以中点为中心,向两边扩展。这样就能避免上述的最坏情况。枚举子串中点时须要分长度为奇数和偶数的情况,详细的能够參考下这两组例子:aabaa,aabb。中点的个数存在

latex=\dpi{100}&space;\fn_jvn&space;N">浅谈Manacher算法与扩展KMP之间的联系

个,每次以中点为中心向两边扩展最坏须要

latex=\dpi{100}&space;\fn_jvn&space;O(N)">浅谈Manacher算法与扩展KMP之间的联系

。所以总时间复杂度为

latex=\dpi{100}&space;\fn_jvn&space;O(N^2)">浅谈Manacher算法与扩展KMP之间的联系

\dpi{100}&space;\fn_jvn&space;O(N^2)" title="O(N^2)" alt="">

,空间复杂度浅谈Manacher算法与扩展KMP之间的联系.
int solution(string &S)
{
const int n = S.size();
int ans = 0;
for (int i = 0; i < n; ++i)
{
//for the odd case
for (int j = 0; (i - j >= 0) && (i + j < n) && S[i - j] == S[i + j]; ++j)
ans = max(ans, j << 1 | 1);
//for the even case
for (int j = 0; (i - j >= 0) && (i + 1 + j < n) && S[i - j] == S[i + 1 + j]; ++j)
ans = max(ans, 2 * j + 2);
}
return ans;
}

解法四

            在解法三中,当枚举以i中点的最长回文子串。须要以i为中点,向两边进行扩展,无疑,最坏情况下会退化到浅谈Manacher算法与扩展KMP之间的联系

\dpi{100}&space;\fn_jvn&space;O(n)" title="O(n)" alt="">

这里,我们能够通过利用字符串的hash来减少时间复杂度(注:不熟悉字符串hash的朋友,能够參考下这篇博客点击打开链接,整理的非常具体)。

如果当前推断的是以i为中点偶数长度的最长回文,对于随意一个长度k,如果S[i
- k + 1....i]的hash值与S[i + 1.....i + k]的hash值不同,那么以i为中点的最长回文子串的长度必然小于2 * k,因此。能够通过该条件进行二分。这样就能在

latex=\dpi{100}&space;\fn_jvn&space;O(lgn)">浅谈Manacher算法与扩展KMP之间的联系

的时间范围内找到最优解。因为每次推断的时间复杂度仅仅须要浅谈Manacher算法与扩展KMP之间的联系

\dpi{100}&space;\fn_jvn&space;O(lgn)" title="O(lgn)" alt="">

,所以该解法的时间复杂度为

latex=\dpi{100}&space;\fn_jvn&space;O(nlgn)">浅谈Manacher算法与扩展KMP之间的联系

,空间复杂度为浅谈Manacher算法与扩展KMP之间的联系

const int BASE = 131, N = 1e+6 + 7;
typedef unsigned long long ULL;
//rec: record forward direction hash value
//rRec:record backward direction hash value
//P: record power of BASE
ULL rec[N], rRec[N], P[N];
int Bin(int len, int end, int rEnd, int __len)
{
int l = 1, r = len;
while (l <= r)
{
int mid = l + (r - l) / 2;
ULL lHash = rec[end] - (end - mid >= 0 ? rec[end - mid] : 0) * P[mid];
ULL rHash = rRec[rEnd] - (rEnd + mid < __len ? rRec[rEnd + mid] : 0) * P[mid];
if (lHash ^ rHash)
r = mid - 1;
else
l = mid + 1;
}
return r;
}
int solution(char *S)
{
const int len = strlen(S);
P[0] = 1ULL;
//calculate power of BASE
for (int i = 1; i < =len; ++i)
P[i] = P[i - 1] * 131;
rec[0] = S[0], rRec[len - 1] = S[len - 1];
//calculate the string <span style="font-family:Microsoft YaHei;">hash </span>value
for (int i = 1, j = len - 2; i < len; ++i, --j)
rec[i] = rec[i - 1] * BASE + S[i], rRec[j] = rRec[j + 1] * BASE + S[j];
int ans = 0;
for (int i = 0; i < len; ++i)
{
int tmp;
//for the even case
tmp = Bin(min(i + 1, len - i - 1), i, i + 1, len);
ans = max(ans, tmp << 1);
//for the odd case
tmp = Bin(min(i, len - i - 1), i - 1, i + 1, len);
ans = max(ans, tmp << 1 | 1);
}
return ans;
}

上述代码有两个地方须要说明一下:1.无符号长整型溢出时,编译器会自己主动取模 2.关于计算P数组。假设是单case,P数组的求解能够放到solution函数中,假设是多case,P数组的求解必须放到外面,由于P数组仅仅用计算一次就能够了.此种解法。能跑过POJ
3974和hdu 3068,感兴趣的朋友能够试试这样的解法.

解法五

          该问题也能够用后缀数组求解,在源字符串末尾加入一个源字符串中未出现过的字符,然后将源字符串的反转串连接在后面,那该问题就转换为在新得到的字符串中求解某两个后缀的LCP。而求解LCP是后缀数组典型的应用。因为后缀数组构造和实现。相比前面简述的几种方法,实现和理解相比之下要困难的多。这里就不做过多解释.

Manacher算法

        前面简述了五种解法,而各种解法的时间复杂度、空间复杂度也不尽同样。这里在介绍一种时间复杂度、空间复杂度均为浅谈Manacher算法与扩展KMP之间的联系的算法:Manacher算法。该算法首先对源字符串进行处理,在源字符串的每个字符前后加一个源字符串中未出现过的字符,比如源字符串为:aba,通过预处理后。源串变为:#a#b#a#。对于新得到的字符串,easy得知,该串没有长度为偶数的回文子串,由于串中没有相邻字符是同样的。这样就避免了讨论奇数、偶数的讨论。
         现定义数组P[i] = x。表示以i为中心[i - x...i + x]是最长且回文的,那么浅谈Manacher算法与扩展KMP之间的联系就是源字符串的最长回文子串的长度。以字符串abaaba为例:
                                                   S :  #    a    #    b    #    a    #    a     #    b    #     a    #
                                                   P :  0    1    0    3    0     1    6    1     0    3     0     1    0
         通过观察P数组,发现其最大值是6,而源串中的最长回文子串abaaba的长度也正好是6。如今。面临的问题是怎么求解P数组?
         如果计算P[i]时。P[0..i - 1]已经计算好了。对于前面的P[x](0 <= x < i)。定义一个框[x - P[x]...x + P[x]],right等于max{x + P[x]}。center值为取到right时的x值。如今要计算P[i],对于i值,这里要分两种情况:
  1. i <= right:  先计算i关于center的对称点i' = 2 * center - i,依据回文串的对称性,从框左边left...i'和i...right是一致的。假设P[i']的值能把i + P[i']的值限定在框里,那么P[i] = P[i'],由于框里的东西已经比較过了。比如源串为babcbabcbaccba,如今要计算P[13]值,例如以下图所看到的:浅谈Manacher算法与扩展KMP之间的联系 
                                                                 

    i = 13关于center的对称点是i' = 9。将[i' - P[i']......i + P[i]]子串取出(这里为了便于叙述,先如果i' - P[i'] >L)。得到例如以下的图: 浅谈Manacher算法与扩展KMP之间的联系 
              通过对照上图能够发现,以i'为中点的最长回文子串S[8..10]相应着S[12...14],也就是说,S[i' - P[i']...i' + P[i']]与S[i - P[i']...i + P[i']]一定是相等的(注:此处的前提条件是i' - P[i'] >L),并且P[i]一定等于P[i'],由于S[i + P[i'] + 1] 一定不等于S[i - P[i'] - 1],这在求P[i']时,就已经比較过了。当i' - P[i'] <= L时,能够得到S[L...2 * i' -
    L]一定是回文子串,而S[L...2 * i' - L]恒等于S[2 * i - R....R]。此时,P[i]的值至少是R - i。而大于right部分的,都是没有比較过的,所以仅仅能以i为中点,以R - i + 1为半径向两边扩展。结合i' - P[i'] > L和i' - P[i'] <= L的情况,能够发现P[i]的值至少等于min(P[i'], R - i),所以,在i < right的情况下。使P[i] = min(P[i'], R - i),然后以i为中心,P[i]为半径,向两边扩展。并更新对应的center和right值就可以.

  2. i > right: 这样的情况下,仅仅能以i为中心,向两边扩展,并更新对应的center和right值。

复杂度分析

          计算过程中,须要用到额外的P数组,而right的值仅仅能添加n次,所以该算法的时间、空间复杂度均为浅谈Manacher算法与扩展KMP之间的联系
const int N = 1e+6 + 7;
char orign[N << 1];
int P[N << 1];
int Manacher(char *S)
{
int len = strlen(S);
S[len << 1] = '#', S[len << 1 | 1] = '\0';
for (int i = len - 1; i >= 0; --i)
S[i << 1 | 1] = S[i], S[i << 1] = '#';
int center = 0, right = 0, ans = 0;
len <<= 1;
for (int i = 0; i <= len; ++i)
{
P[i] = i <= right ? min(P[2 * center - i], right - i) : 0;
while (i - P[i] - 1 >= 0 && i + P[i] + 1 <= len && S[i - P[i] - 1] == S[i + P[i] + 1])
++P[i];
if (i + P[i] > right)
right = i + P[i], center = i;
ans = max(ans, P[i]);
}
return ans;
}
           前面已经讲述了Manacher算法的工作原理。这里谈一下Manacher算法的应用.

应用一:回文子串个数

         对于一个给定串S,是否能在线性时间复杂度内求出该字符串有多少个回文子串?
        答案是肯定的,统计存在多少个回文子串。仅仅用统计以i(0 <= i < len(S))为中心、长度为偶数的回文子串数量和以i为中心长度为奇数的回文子串数量。然后累加就可以。

如果如今须要求解以i为中心、长度为奇数的回文子串数量。仅仅须要找到以i为中心、长度为奇数的最长回文子串的长度值,然后将长度值加一除2。即为所求的解。偶数的处理方式一样。而在求解最长回文子串的长度时,计算出来的P[i]值。就已经计算出了以源串全部点为中心、长度各自是偶数和奇数的最长回文子串的长度。仅仅须要线性遍历一遍P[i]数组,将(P[i]
+ 1) / 2的值累加,就是S的回文子串的个数。

应用二:扩展KMP

         给定一个串S[0...n],是否能在线性时间复杂度内求出P[i] = LCP(S[i...n],S[0...n])(1 <= i <= n)?
         对于该问题,我们能够套用Manacher算法。

现计算P[i],如果P[1...i - 1]都已经计算好了,设定right为max(P[x] - 1 + x)(1 <= x < i)。left为取到right值时的x值。(1)当right >= i时,通过已经计算出来的P[1..i-1]值,我们可知S[left....right] = S[0...right
- left]。找到i的位置相当于S串的开头的位置:i' = i - left,假设i + P[i'] <= right。那么非常easy得出P[i] = P[i']。假设i + P[i'] > right,那么P[i]的值至少为right - i + 1,综上两个情况,易知P[i]值至少为min(P[i']。right - i + 1),然后暴力比較,并更新对应的left和right。因为right的值仅仅能添加n次。所以该算法是浅谈Manacher算法与扩展KMP之间的联系

        当然了,上述的算法并不局限于与串自身匹配LCP。比方给定两个串S、T,要在S串中查找是否出现T串,用一个在S、T中都没有出现的字符连接T和S,这里如果为'#'。得到新串T#S,最后在推断P数组中是否存在值为len(T)的元素就能推断T串是否在S串中出现。而在扩展KMP中。对于模式串T,须要计算LCP(S[i...n],T)(0 <= i <=
n)。相同能够利用上述的方法在浅谈Manacher算法与扩展KMP之间的联系的时间范围内求解,这也是Manacher算法与扩展KMP算法的相似之处。
上一篇:[BSGS算法]纯水斐波那契数列


下一篇:Android NDK学习(五):Java调用Native代码流程总结