Manacher算法筆記

2019-11-14 12:12:03

字體：大中小

供稿：網(wǎng)友

定義：

一種簡單的尋找回文子串的算法。可以在O(N)的時間復(fù)雜度內(nèi)，求出以每個字母為對稱中心的回文子串。

屬于奇技淫巧？回文串的題很少啊。我們還有后綴數(shù)組求回文子串的方法，可以做到O(Nlog2N) $O(Nlog_2N)$ ，但是寫起來煩，(主要是我不會寫)。

模板

#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;

說明

定義一些符號：

原串:S0 $S_0$ 處理后保證奇數(shù)長度的串:S $S$ 反串:S′ $S'$ (即為S $S$ 前后倒置的串) 數(shù)組:P $P$ 記錄以每個字符為中心的最長回文半徑的數(shù)組(最小為1，即只含有其本身)

預(yù)處理

將S0 $S_0$ 兩個兩個字符之間插入不屬于原字符集的字符，將其轉(zhuǎn)化為S $S$ 。

引理

P[i]?1 $P[i]-1$ 是以Si $S_i$ 為中心的回文子串在原串中的長度。

算法

我們接下來還要再定義兩個數(shù)字，即：

MaxId $MaxId$ 為之前的回文串中匹配到的最遠(yuǎn)位置 id $id$ 就是MaxId $MaxId$ 被取到時的i $i$ 點

對于i′=2?id?i $i'=2*id-i$ ，容易看出i′ $i'$ 和i $i$ 關(guān)于id $id$ 對稱。但如果這一部分的回文串，翻過去超出了MaxId $MaxId$ ，那我們就不能保證原有的對稱性。那么為了保證正確性，我們在這兩種可能性中取最小，最終我們有P[i]=min{P[2?id?i],MaxId?i} $P[i]=min/{P[2*id-i],MaxId-i/}$ 。但此時的P[i] $P[i]$ 不是最佳解，而只是最小值。我們通過迭代，可以求到P[i] $P[i]$ 的最優(yōu)解。最終統(tǒng)計時，統(tǒng)計P $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]); }