【例題】
點選這裡
【思路】
最長回文子串是個非常經典的問題,Manacher算法是解決它的O(n)優秀算法。
該算法提出在字元串相鄰字元間插入字元,進而在中心拓展時無需考慮串長度的奇偶性(顯然,對于任意長度為n的串,有n-1個間隔,故而補全串長度為2n-1,總為奇數)。
舉個例子:原串str為abababa,長度為7。則補全串s為$#a#b#a#b#a#b#a#*,長度為17。其中#、$和*不屬于原串字元集合,#為插入字元,$和*用來标記補全串邊界,這友善了中心拓展比較,同時避免索引溢出。
設數組r,r[i]表示補全串s中,以字元s[i]為中心的回文串半徑長度(半徑含中心字元s[i])。
![](https://img.laitimes.com/img/_0nNw4CM6IyYiwiM6ICdiwiIyVGduV2QvwVe0lmdhJ3ZvwFM38CXlZHbvN3cpR2Lc1TPB10QGtWUCpEMJ9CXsxWam9CXwADNvwVZ6l2c052bm9CXUJDT1wkNhVzLcRnbvZ2LcZXUYpVd1kmYr50MZV3YyI2cKJDT29GRjBjUIF2LcRHelR3LcJzLctmch1mclRXY39TNzUDO1YzM3EDMxIDM2EDMy8CX0Vmbu4GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.jpg)
一旦得出數組r,則隻需周遊r并将ans置為最大的r[i]值,輸出ans-1即為原串中回文串的最大長度。
可以證明,經過上面的補全後,對于任意i,補全串中以s[i]為中心的回文串去掉所有#後,長度為r[i]-1,即對應的原串中回文子串的長度。
如何求出數組r呢?顯然在求r[i]時,要充分利用r[1]、r[2]……r[i-1]這些已經求出的資訊。先在這裡寫出數學表達。
由集合Q确定r[i]的最小值後,還需嘗試性地增大r[i]向外圍擴充比較,直到遇見s[i-r[i]]≠s[i+r[i]],則已找到以s[i]為中心的最長回文串。
上面的數學表述雖然嚴謹,但不夠具象,下面對該數學形式作通俗闡述。
事實上,j+r[j]反映了1,2……i-1中已經找到的所有回文串的最大覆寫範圍。如果j+r[j]<i,則前面的結果對求r[i]并沒有作用,我們隻能暫時置r[i]=1(一個字元本身,也是一個回文串),然後再向外拓展比較。否則,i則在前面的覆寫範圍内,那麼首先找到s[i]關于s[j]的對稱字元s[j*2-i],則s[i]、s[j*2-i]距以s[j]為中心的回文串邊緣的長度均為j+r[j]-i,根據回文串的對稱性可得,若r[j*2-i]< j+r[j]-i(以s[j*2-i]為中心的回文串是以s[j]為中心的回文串的子串),則在覆寫範圍内可以确定r[i]=r[j*2-i] ; 若r[j*2-i]> j+r[j]-i,則以s[i]為中心的回文串可一直拓展至覆寫邊緣。覆寫範圍外的部分,則需要我們嘗試增大r[i],繼續老老實實地比較。
更形象的表述,則可見下圖(綠色為重疊部分,藍色為s[j]中心串,黃色為s[j*2-i]中心串突出部分):
【代碼】
#include <stdio.h>
#include <string.h>
#define maxSize 1000010
#define min(x,y) (x<y)? x:y
long int manacher(const char *str)
{
long int i,len=strlen(str);
char s[maxSize*2+3];
s[0]='$'; s[len*2+1]='#'; s[len*2+2]='*';
for (i=0;i<len;i++) {s[2*i+1]='#'; s[2*i+2]=str[i];}
long int r[maxSize*2+3], j=1; r[1]=1;
for (i=2;i<=len*2;i++)
{
if (r[j]+j>i) r[i]=min(r[j]+j-i, r[2*j-i]); else r[i]=1;
while (s[i-r[i]]==s[i+r[i]]) r[i]++;
if (i+r[i]>j+r[j]) j=i;
}
long int ans=0;
for (i=1;i<=len*2;i++) if (r[i]>ans) ans=r[i];
return ans-1;
}
int main()
{
char str[maxSize];
int n,i;
scanf("%d",&n);
for (i=0;i<n;i++){scanf("%s",str); printf("%d\n",manacher(str));}
return 0;
}