程式員程式設計技術學習筆記——最長回文子串

程式員程式設計技術學習筆記——最長回文子串

1. 題目描述

    給定一個字元串，求它的最長回文子串的長度。例如：abaaaabaaa的最長回文子串就是以b為中心，長度為7的回文子串aaabaaa.

2. 解法1：中間擴充法

    我們可以以字元串中每一個字元為中心，往左右兩邊擴充，在滿足回文字元串條件下，能夠擴充的最大長度就是回文子串的長度。注意：這種方法需要考慮子串長度奇數/偶數的不同情況。整個過程如下圖：

上述方法需要注意奇數和偶數情況的不同，一個不同在于邊界（奇數為i-j和i+j;偶數為i-j和i+j+1)；另一個不同是長度（奇數是2*j+1；偶數是2*j+2)。也正是因為這種方法需要分情況讨論，導緻有麻煩的缺點。而且，周遊每一個字元為中心的時候，始終都要從j=1開始周遊，時間複雜度也比較大。

    這種解法的代碼如下：

#include<iostream>
#include<string.h>
using namespace std;

int LongestPalindrome(char *str, int len)
{
	int i, j;
	int maxlen=0, templen;
	for(i=0; i<len; i++)  //±éÀúÿ¸ö×Ö·û
	{
		for(j=0; (i-j)>=0 && (i+j)<=len; j++)
		{
			if(str[i-j]!=str[i+j])
                break;
            templen=2*j+1;
		}
		if(templen>maxlen)
            maxlen=templen;

        for(j=0; (i-j)>=0 && (i+j+1)<=len; j++)
        {
            if(str[i-j]!=str[i+j+1])
                break;
            templen=2*j+2;
        }
        if(templen>maxlen)
            maxlen=templen;
	}

	return maxlen;
}

int main()
{
	char str[10]="abaacaa";
	int len=strlen(str);

	int maxlen=LongestPalindrome(str, len);
	cout<<maxlen<<endl;

	return 0;
}
           

3. 解法2：Manacher算法

    Manacher算法是專門用來解決最長回文子串問題的一種算法，其時間複雜度可以達到O(n)，其中n是字元串的長度。

    從上面解法演變到這個算法的邏輯過程還是這樣的：上面算法比較麻煩的是需要讨論奇數偶數的情況，而且每次以第i個字元為中心擴充的時候，都要從長度為1開始擴充，導緻了時間複雜度比較大。那麼我們能不能讓串的長度始終都是奇數呢？（因為奇數的情況更加簡單一些）再有，我們能不能讓後面幾次的擴充可以用到前面擴充的先驗資訊，進而減少時間複雜度呢？

    Manacher算法就是從上面兩個方面實作優化的。

    優化1：首先通過在每個字元的兩邊都插入一個特殊的符号，将所有可能的奇數或偶數長度的回文子串都轉換成了奇數長度。比如 abba 變成 #a#b#b#a#， aba變成 #a#b#a#。此外，為了進一步減少編碼的複雜度，可以在字元串的開始加入另一個特殊字元，這樣就不用特殊處理越界問題，比如$#a#b#a#。以字元串12212321為例，插入#和$這兩個特殊符号，變成了 S[] = "$#1#2#2#1#2#3#2#1#"。這一步就讓串長變成了奇數。

    優化2：然後用一個數組 P[i] 來記錄以字元S[i]為中心的最長回文子串向左或向右擴張的長度（包括S[i]）。最長回文子串的長度就是P資料中最大值-1. 那麼顯然，這種算法的關鍵之處就是如何求得算法P，求數組P的過程就實作了後面的數可以用到前面的數的先驗資訊，進而減少了時間複雜度。

    我們可以通過下圖來展示如何求資料P：

首先我們引入兩個輔助變量id和mx，其中id表示最大回文子串中心的位置，mx則為id+P[id]，也就是最大回文子串的邊界。id和mx初始化都是0。在求第i個字元處可擴充的回文子串時，我們可以針對i和id的相對位置分情況讨論：

1）當i+P[ j ]<mx的時候，以i為中心，P[ j ]為半徑擴充的子串就已經在以id為中心mx為範圍的子串中了。這時，我們就可以直接用i相對于id對稱點j的P[ j ]資訊，即P[ i ]=P[ j ]。如下圖：

2）當i+P[ j ]>=mx的時候，以i為中心，P[ j ]為半徑擴充的子串就跳出以id為中心，mx為範圍的子串中了。這時，我們可用的先驗資訊就是P[ i ]>=mx-i，也就是我們隻能确定P[ i ]的最小值。如下圖：

然後我們再以i為中心，P[ i ]為半徑擴充，如果滿足回文條件，P[ i ]繼續增加。換句話說，剛才求得的P[ i ] 隻是一個初始值，我們需要繼續擴充判斷。

3）當i>=mx的時候，我們也是隻能确定P[ i ]的最小值，但是此時由于i已經跳出了mx的範圍，是以我們無法用到前面的先驗資訊，隻能認為P[ i ]的最小值為1，這也是最長回文子串的最小長度。然後我們再進行回文判斷。

   代碼如下：

//輸入，并處理得到字元串s
int p[1000], mx = 0, id = 0;
memset(p, 0, sizeof(p));
for (i = 1; s[i] != '\0'; i++) 
{
    p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;
    while (s[i + p[i]] == s[i - p[i]]) 
        p[i]++;
    if (i + p[i] > mx) 
    {
        mx = i + p[i];
        id = i;
    }
}
//找出p[i]中最大的
           

    至此，Manacher算法介紹完畢。我們回頭再來看，其實Manacher算法就是把原來的字元串加入了一些标記符号，使得串長始終都是奇數，然後再以id和mx兩個輔助變量，快速地對P[ i ]指派，進而在計算以i為中心的回文子串的過程中，不必每次都從1開始比較，減少了比較次數，最終使得求解最長回文子串的長度達到線性O(N)的時間複雜度。