定義：
一種簡單的尋找回文子串的算法。可以在O(N)的時(shí)間復(fù)雜度內(nèi)，求出以每個(gè)字母為對(duì)稱中心的回文子串。
屬于奇技淫巧？回文串的題很少啊。 我們還有后綴數(shù)組求回文子串的方法，可以做到O(Nlog2N)，但是寫起來煩，(主要是我不會(huì)寫)。
#define min(a,b) ((a)<(b)?a:b)void Manacher(char *a) { int MaxId,id; for(int i=1;a[i]!='/0';i++) { if(MaxId>i) p[i]=min(p[2*id-i],MaxId-i); else p[i]=1; while(a[i+p[i]]==a[i-p[i]]) p[i]++; if(p[i]+i>MaxId){ MaxId=p[i]+i; id=i; } } }/*以下是構(gòu)造的片段*/for(i=1;b[i]!='/0';i++) { a[i<<1]=b[i]; a[(i<<1)+1]='#'; }a[0]='?',a[1]='#';n=(i<<1)+2,a[n]=0;說明
定義一些符號(hào)：
原串:S0 處理后保證奇數(shù)長度的串:S 反串:S′(即為S前后倒置的串) 數(shù)組:P 記錄以每個(gè)字符為中心的最長回文半徑的數(shù)組(最小為1，即只含有其本身)
預(yù)處理
將S0兩個(gè)兩個(gè)字符之間插入不屬于原字符集的字符，將其轉(zhuǎn)化為S。
引理
P[i]?1是以Si為中心的回文子串在原串中的長度。
算法
我們接下來還要再定義兩個(gè)數(shù)字，即：
MaxId 為之前的回文串中匹配到的最遠(yuǎn)位置 id 就是MaxId被取到時(shí)的i點(diǎn)
對(duì)于i′=2?id?i，容易看出i′和i關(guān)于id對(duì)稱。但如果這一部分的回文串，翻過去超出了MaxId，那我們就不能保證原有的對(duì)稱性。那么為了保證正確性，我們?cè)谶@兩種可能性中取最小，最終我們有P[i]=min{P[2?id?i],MaxId?i}。但此時(shí)的P[i]不是最佳解，而只是最小值。我們通過迭代，可以求到P[i]的最優(yōu)解。最終統(tǒng)計(jì)時(shí)，統(tǒng)計(jì)P數(shù)組的最大值即可。
HDU3068
裸題。 (也沒什么好題了)
#include <stdio.h>#define M 110010char b[M],a[M<<1];int p[M<<1];#define min(a,b) ((a)<(b)?a:b)#define max(a,b) ((a)>(b)?a:b)int main() { int i,n,id,MaxL,MaxId; while(scanf("%s",b+1)!=EOF) { MaxL=MaxId=0; for(i=1;b[i]!='/0';i++) { a[i<<1]=b[i]; a[(i<<1)+1]='#'; } a[0]='?',a[1]='#'; n=(i<<1)+2,a[n]=0; for(i=1;i<n;i++) { if(MaxId>i) p[i]=min(p[2*id-i],MaxId-i); else p[i]=1; while(a[i+p[i]]==a[i-p[i]]) p[i]++; if(p[i]+i>MaxId) { MaxId=p[i]+i; id=i; } MaxL=max(MaxL,p[i]); }
