manacherアルゴリズム(マラ車)
4178 ワード
このアルゴリズムは通常,1つの文字列の中で最も長い文列の長さがどれだけあるかを解決するために用いられるが,うんうん,次いで時間複雑度はO(n)であるが,使用範囲には限界があるが,やはり有用である.(ポイントは短いショートカット)いくつかのものを定義r[i]iを回文の中心とする最大回文半径を表す栗:a b a b a回文半径:1 1 2 1はっきりしていると思います.mx:見つかった回文列を表す最右境界p:mxの回文中心を表す.j:i pについての対称点mx’:mxがpについての対称点を表す奇偶性を避けるために、各文字の間に特殊な記号を付けてもいいし、何でもいいし、首尾の記号が他なら同じではないので、栗again@a^b^a^b^a*を挙げて、人の心を奮い立たせる時が来たので、分類してj.......mx’…………p…………..mx…………….i ______________________________________________________ これは、mx=1(下限は1であり、最小はそれ自身のみであり、上限は未知であるため)、非>=2であることを覚えておいて、当然とは思わないでください.次に、2つ目のケースmx’............を示します.j…………………….p…………………..i……………………………….mx————————————————————————————————————————————————————————————これはまた2つの状況に分けることができる第1のmx-i>r[j]つまりjの回文半径はmxに達しないことを意味し、またpの左右の両側が対称性を持っているため、r[i]=r[j]はjの回文半径が最大境界の対称点mxに達しないため、したがってiも最大境界mxに達しない.第2のmx−i<=r[j]は、上とは逆にjが最大境界を越えることができるので、r[i]の上限は未知であり、下限はmx−i、すなわちr[i]>=mx−iである.上限については、1人1人で一致すればいいと思います.答えは最大半径か最大半径-1だと思います(境界がアルファベットかどうかを見てみましょう)偽コード(正しいと思います)pascal
はっきりしないところをお許しください.アルゴリズムの別名:馬が車を引く時間の複雑さの証明を引き延ばします:(私も分かりません)だから神のガリガリのブログを探して見てみて、大意はmxの右に移動する回数がnより小さいです
uses math;
var
s,s1:string;
r:array[-10000..10000]of longint;
mx,p,j,mx1,i,n,zd:longint;
begin
//assign(input,'ma.in');
// reset(input);
read(s);
n:=length(s);
s1:='#';
for i:=1 to n do
begin
s1:=s1+s[i]+'$';
end;
delete(s1,length(s1),1);
s1:=s1+'@';
for i:=1 to length(s1) do
begin
if(mx<=i)then
begin
r[i]:=1;
end
else
begin
r[i]:=min(r[2*p-i],mx-i);
end;
while(s1[i-r[i]]=s1[i+r[i]])do inc(r[i]);
if(i+r[i]>mx)then
begin
p:=i;
mx:=i+r[i];
end;
end;
for i:=1 to length(s1) do
begin
if(s1[i+r[i]-1] in ['a'..'z'])then zd:=max(zd,r[i])
else zd:=max(zd,r[i]-1);
end;
writeln(zd);
end.
はっきりしないところをお許しください.アルゴリズムの別名:馬が車を引く時間の複雑さの証明を引き延ばします:(私も分かりません)だから神のガリガリのブログを探して見てみて、大意はmxの右に移動する回数がnより小さいです