27

ウォークからの最大次数2の最小グラフ推論

Inferring a minimum graph of bounded degree 2 from a walk成定 真太郎ディプタラマShintaro Narisada

ヘンリアン

Diptarama Hendrian

吉仲 亮
Ryo Yoshinaka

篠原 歩
Ayumi Shinohara

東北大学 大学院情報科学研究科
Graduate School of Information Sciences, Tohoku University.

1

導入

表1: 次数2の最小グラフ推論問題における計算量

辺集合 V , 頂点集合 E とラベル c:Earrow\Sigma からなるラベル付き無向グラフ G=(V, E, c) を考える.の隣接した頂点をたどる列 v_{0}, e_{1}, v_{1},Gv_{n-1}, e_{n}, v_{n}(ここに v_{i}\in V, e_{i}=(v_{\iota-1}, v_{i})\in E である) を G
上のウォークといい,そこで遭遇する辺ラベルの列c(e_{1}), c(e_{2}) ,c(e_{n}) をそのウオークの出力と呼ぶ.

ウォークからの最小グラフ推論問題とは,入力として与えられた文字列 w に対して,出力が w となる1の頂点も含む) に大別される.線形鎖において,始ウォークを持つグラフで,頂点数が最小のものを見点と終点が共に次数1の頂点であるウォークを両端つける問題である.図1に一例を示す.

ウォークといい,その制限がないものを一般ウォー

Aslam ら [1] は,この問題を定式化し,最大次数をクと言う.Raghavan [4] は,ウォークからの閉路グ2に制限したグラフ族に対して,ウオークからの最小ラフの推論問題と,一般ウォークからの線形鎖の推グラフ推論問題に対する多項式時間アルゴリズムを論問題が,ともに両端ウォークからの線形鎖の推論提案した (表1).最大次数2の連結グラフは,閉路問題に O(n) 時間で帰着できることを示し,またこの問題に対する O(n\log n) 時間アルゴリズムを与えグラフ (次数2の頂点のみからなる) と線形鎖 (次数た.また,任意の定数 k\geq 3 に対し,次数 k のグラ\underline{abc}a-\cdot\verline{\sim}\simeq_{- - =^{-\cdot-}^{\sim}- - - =^{-}\sim-\simrghtarow-\cdot=_{- - -}^{\simrghtarow\sim- \overline{-} .\sim-\sim

フを推論する問題が NP 困難であることを証明した.

一方,Maruyama ら [3] は,ウォークからの最小木推論問題に対して, 0(n) 時間アルゴリズムを提案した.また,複数の部分ウォークからの最小木および最小線形鎖推論問題が NP 完全であることを示した.

本論文は,前述の両端ウォークからの最小線形鎖

図1: 出力が abcaacbbbaabccbbca となるウォーク推論問題に対して,Manacher の極大回文を求めるをもつ最小の線形鎖アルゴリズムを応用した 0(n) 時間領域アルゴリ

2828
R を \Sigma^{*} 上の二項関係とし,ズムを提案する.このことにより,ウォークからの最大次数2の最小グラフ推論問題がすべて 0(n) 時書く.

間で解けることが導かれる (表1最下段) .

約であるとは,ないときをいう.

2準備\Sigma^{*} の要素を文字列という.文字列 w の長さを |w| と表し,空\Sigma^{*}-\{\varepsilon\} と書く. 1\leq i\leq|w| に対して, w[i] を w のi 番目の文字とする.文字列

w=xyz に対して,対し,xR^{*}y となる既約な文字列 y を呼び,\hat{x}\forall w, x, y\in

1\leq i\leq j\leq|w| に対して,i で始まりxの正規形と\Sigma^{*} 上の二項関係 arrow を次式で定義

し,この書き換え処理を,( arrow の関係の下)Z 形を縮arrow=\{ (pxx^{R}xq, pxq) |x\in\Sigma^{+},p, q\in\Sigma^{*}\}

x,j で終と書く.

約するという :をそれぞれ w の接頭辞,部分文字列,接尾辞と呼ぶ.

R が合流性をもつとは,きをいう.合流性をもつ関係 R と文字列 x\in\Sigma^{*} に文字列を \varepsilon と書く.空でない文字列の集合を \Sigma^{+}=

zxRy となる文字列 y\neq x が存在し\Sigma^{*}, wRx\wedge wRy\Rightarrow ヨ z\in\Sigma^{*}, xR^{*}z\wedge yR^{*}z であると

大きさ \sigma のアルファベットを \Sigma とし,y,(x, y)\in R を xRy とR^{*} を R の反射推移閉包とする.文字列 x が既定理1 ([1]) 二項関係 arrow は合流性を持つ.

わる w の部分文字列を w [i..j] と書く.文字列 x の逆定理1より,任意の順番で ( arrow の関係の下) 文字列 xx^{R}=x[|x|]\cdots x[1] と表す.文字列 p が偶 を有限回数縮約することで,正規形 \hat{x} が求まる.こ回文であるとは,文字列 x\in\Sigma^{*} に対して p=xx^{R}のとき, Z(\hat{x})=\emptyset である.

文字列をとなるときをいい,この長さ r=|x| を半径と呼ぶ.

本稿では,偶回文のみを扱うので,以下,偶回文の定理2 ([1]) 文字列 w が両端ウォークとなる最小のことを単に回文と呼ぶ.

線形鎖は二項関係 arrow の正規形 \hat{w} である.

wを長さ n の任意の文字列とする.

タ1」 w[b..e] が回文であるとき,wの部分文字

p=w[b..e] を w の回文部分文字列と呼び,位置 i= \frac{b+e}{2} を p の中心と呼ぶ.特に,
e=nw[b-1]\neq w[e+1],を満たすとき,b=1 ,またはp を i を中心とする極大回文と呼ぶ.中心 c , 半径 r の極大回文を2つ組 (c, r) で表す.文字列 w 中の極大回文の集合を P(w) と書く.
P_{j}(w)=\{(c, r)\in P(w)|c<j\} と書く.また,

P_{\iota,j}(w)=\{(c, r)\in P(w)|i<c<j\} と書 \langle.

例2
ゆz=xx^{R_{X}} となるときをいう.

z=w[b..e] が Z 形であるとき,位置 c=\frac{2b+e-2}{3} をピボッ
ト, r=\frac{e-b+1}{3} を半径と呼び,2つ組 \langle c, r\rangle で表す.
文字列 w 中の Z 形の集合を Z(w) と書く.
例1

w=ababccbaabca において,Z 形abccbaabcを表す.

する.

cb\underline{aaa} abccbaabba

arrow

Z形cbaabccbaabba

arrowと異なる書き換え順でも最終的には面が得られる.

3

両端ウォークからの最小線形鎖推論
定理2より,両端ウォークからの最小線形鎖推論

は,入力文字列 w に対して,以下の処理を行えばよいことが分かる.

(1)

wの部分文字列に Z 形 xx^{R_{X}} が見つかった場合,xx^{R_{X}} の接尾辞 x^{R_{X}} をはピボット5, 半径3である.すなわち, \langle 5, 3} である.

Z_{J}(w)=\{\{c, r\}\in Z(w)|c<j\} とし, Z_{i_{j}},(w)={ \langle c, r\rangle\in Z(w)|i<c<j または i<c+r<j } とcbaaaabccbaabba とすると,最小線形鎖

cbaabccba arrow cba. なお arrow の合流性により,上記文字列 z が Z 形であるとは,空でない文字列 x\in\Sigma^{+} に対して,w==cba は次のように求められる.下線部は(2)wから取り除く.

wの部分文字列中に Z 形が1つも存在しなくなるまで処理 (1) を繰り返す.

29
長さ の入力文字列n

い文字 $ と \# を用いて,wに対して,
w

w

中に出現しな —hm
1:RecManacher(w)\underline{Algorlt}

w[n+1]=\# と[0]={\},約束する.本問題を解くアイデアとして, Z 形 xx^{R_{X}} 1 Pals [0]=0 ;は,

2 つの回文xx^{R} と x^{R_{X}} がそれぞれ半分ずつ重なったものと考えられることから,Manacher のア

ルゴリズム [2] を利用して Z 形の検出および縮約を行う.文字列 w のすべての位置 i に対し,i を中心と2 i=2 ;3 whilew[i-1]\neq\# do(i-1, i)

45 \lflo r i=i+1;i=mana cher;

する極大回文の半径を格納する配列 Pals を考える.6 return Pals;
Pals [i|=\{r|w[i-r+1..i+r] がi を中心とする

すなわち,w

Algorithm 2: manacher(c, i)の極大回文}.

1i= extension (c, i) ;P(w)=\{(i, Pa1s[i])|1\leq i\leq n\} となるようにPals を求めたい.Pals は,Manacher のアル2i= transfer (c, i) ;3 return i.

’

ゴリズムによって O(n) 時間 . 領域で求めることができる.以下に Manacher のアルゴリズムを再帰的に記述したアルゴリズム RecManacher を示す.

Algorithm 3: extension(c, i)
1r=i-c-1;j=c-r ;2 while3.1

w[i]=w[j] do

3 \lfloor r=r+1;j=j-1;i=i+1

RecManacher アルゴリズム

RecManacher ア)レゴリズムを Algorithm 1に示す.また,Algorithm 2 — 4に Algorithm 1によって呼び出される関数 manacheT (c, i) , extension (c, i) ,;4 Pals [c]=r ;5 return i ;transfer(c, i) をそれぞれ示す.関数 extensi。n(c, i) いて,c'=c+1, ..., c+r の順に,極大回文 Pals [c]は,中心が である極大回文の半径 を求める関数 の左側の情報を用いて Pals [c'] を求める.その際,である.ただし,事前条件として,中心を とする半 (c', r')\in P(w) に対して, c'+r'>c+r となった場合,径 i-c-1 以上の回文が存在することが分かってい すなわち, c' を中心とする極大回文が, を中心とす
rcccる.また,transfer(c, i) は,c'=c+1,c+rの順 る極大回文の右端を越える場合,Algorithm 2の関数に c' を中心とする極大回文の半径を求める関数であ manacher(,を) 引数 (c', c+r+1) によって再帰的に呼る.ただし,途中で極大回文 (c', r') が c+r<c'+r ’となる場合,に呼び出す.

cび出す.Algorithm 1において,manacher (i-1, i) のをシフトしmanaCher(c’, i) を再帰的 処理が終了して返り値 i_{2} が戻されたとき,すなわち,本アルゴリズムの大まかな流れを以下に記す.

i-1までの Pals が全て求まっていると仮定すると,Algorithm 1の RecManacheT(w) において,文字タ1」 w のある位置

i-1について,Algorithm 2のmanacher (i-1, i) を呼び出す.manacher (i-1, i)i_{2}=manacher(i-1, i) となるときを考える.関係=\{((c, r), (c', r'))|(c, r)\in P(w), (c', r')\in
P(w), c<c'\leq c+r<c'+r' } と定義し,このコを用いて, RMostPal_{w}(c) を次に定義する (図2).
コをコRMostPal_{w}(c)= \max\{c'+r'+1|(c, r)\in P(w), (c, r)\sqsupset^{*}(c', r')\}.
は,Algorithm 3の extension (i-1, i) を呼び出し,c=i-1 を中心とする極大回文の半径 r を求める.Algorithm 1において, i_{2}=manacher(i-1, i) がその後,Algorithm 4の transfer (c, c+r+1) にお 求まったとき, i_{2}=RMostPal_{w}(i-1) となる.この30
30Algorithm 4: transfer(c, i)
1\frac{1c_{1\mapsto}^{\dot{j} r_{1_{:}- ^{\dot{j} }{1 \dot{i}1,!}r=i-c-1;d=1 ;2 while d\leq r do\frac{1;:C_{2i_{-r_{2\neg}}}}{111}1432098657 \ovalbx{tsmREJCT}|_{d=+\imath;^Pls[c']=r-d}\fo|_{+1;Pals[c']=r-d|_{+1;}^Pal\mthc{S}[']=r_l;ifw\neq[2*c'-+1]thn}
15

returni;c -r_{-}c+r

図3:

Z 形

\{i, r\rangle と2つの極大回文 (c_{1}, r_{1}) , (c_{2}, r_{2})との関係
c_{2}-r_{2}\leq c_{1} である.

図3に観察1を図示する.観察1を用いて,Algo‐rithm 1に基づいて Z 形を検出することを考える.配列Pals の値を用いて,観察1における式 c_{2}\leq c_{1}+r_{1}
かつ c_{2}-r_{2}\leq c_{1} を表すと,c_{2}\leq c_{1}+Pa1s[c_{1}] かつc_{2}-Pals[c_{2}]\leq c_{1} となる.Algorithm 5は,Algo‐rithm 3のwhile ノレープの内部に Z 形{cĨ, c_{2}-c_{1}\rangle を検出し,これを縮約する命令を挿入したものである.

Algorithm 5の4行目における式 Pals[j-1]\geq rが真となる場合に,Z 形w[j-r..i] が検出される.
Algorithm 5の4行目における式 Pals[j-1]\geq r は,

\frac{1,---}{|1!}\frac{11!1}{11!}Algorithm 5: zextension(c, i)
RMostPal_{w}(c)\frac{1:11}{1I\primec::r1}t\frac{I\prime A.\sim}{I1I}1

図2: RMostPal_{w}(c) と極大回文との関係

とき,0 から i_{2}-1いる.次に,までの極大回文が全て求まってi=i_{2}+1 に対して,manacher (i-1, i)を行う.このとき,i-1

までの Pals が全て求まっている.これを,w[i-1]=\# となるまで繰り返すことで,最終的に P(w) を得る.RecManacher アルゴ
リズムは,長さ n の文字列 w に対して O(n) 時間領域で Pals を計算できる.

1

r=i-c-1;j=c-r ;2 whilew[i]=w[j] do76543 \lfo r\dot{j}\dot{j}-1;\dot{i}=+l;r= +1;

ifals[Pj-,1ret]\geqruth\rnjlfo r_{=}^{del te(\d;ot{2}^{i);} en-1

sPals[c]=r ;9 return i ;式 c_{2}\leq c_{1}+Pals [c_{1}] かつ

c_{2}- Pals

いて,とおいた場合と同様であc_{1}=j-1,る.これにより,3.2

RecManacher を用いた Z 形の検出

観察1 (極大回文と Z 形との関係) \{i, r\rangle が w の Z形である \Leftrightarrow c_{1}=i, c_{2}=i+r に対する w の極大
回文 (c_{1}, r_{1}) と (c_{2}, r_{2}) について,c_{2}\leq c_{1}+r_{1} かつ

c_{2}=cw[c_{2}]\leq c_{1} にお中の一部の Z 形が検出可能となる.この関係をうまく利用し,すべての Z 形が検出できるようなアルゴリズムを考える.
Z 形を検出した後,すなわち,Z 形の縮約を行うことを考える.

w=w_{0}arrow w_{1}arrow\ldotsarrow w_{m-1}arrow w_{m}= ゆとする.Algorithm 5の5行目に,w_{k}[j..i] を削除す

3131
る関数 delete (j, i) を書 \langle . Algorithm 5の4行目において Z 形である

xx^{R}x=w_{k}[j-r..i] が検出され,にそれぞれ示す.関数 laextension(c, i) は,中心がである極大回文の半径を求める関数である.事前

cdelete (j, i) において接尾辞 x^{R}x=w[j..i] が削除され条件として,中心を c とする半径

たとする.その後,文字列 w_{k+1}=w_{k}[1..j-1]w_{k}[i+回文が存在することが分かっている.ただし,ある1\ldots|w_{k}|] において,アルゴリズム中の変数 i=j-1r'>0 に対して,i-c-1 以上の\langle c-r', r' } \in Z(w_{k}) が検出される場

として,RecManacher の処理を再開したい.しかし,合は,縮約後の文字列 w_{k+1} に対する配列 Pals_{w_{k+1}} に関しは,て,次の観察を得る.

を中心とする極大回文の半径を求める関数である.

観察2 ( Z 形の縮約後の文字列の性質) いま,について,i-r-1c-1まっていると仮定する.

c=までの Pals が全て求

j=c-r において,形 :xx^{R_{X}}=w_{k}[j - r..i] が検出され,
辞 x^{R}x=w_{k} [j..i] が削除されたとすると,削除後の文字列 w_{k+1}=w_{k}[1..j-1]w_{k}[i+1\ldots|w_{k}|] において,P_{j-1}(w_{k})=\{(l, Pals [l])|0\leq l<j-1\} が成立するとは限らない.

このようになる原因は,検出による

よって,

w_{k} では

xx^{R}x=w_{k}[j-r..i] のx^{R}x=w_{k}[j..i] の削除に

Z 形

Z 形の接尾辞

j-1 で終端する極大回文が,w_{k+1}w_{k}c'

これらの関数を再帰的に呼び出すことで,ゆを求め

Algorithm 6: LAmanacher(w)1 Pals[0]=0 ;2 Let Stack be an empty stack;
3i=2 ;

4 whilew_{k}[i-1]\neq\# do675 \lf o r i= +1;\dot{i}=lamanacher(i-1, i);Stack.clear()
return \hat{w} ;sにおいてさらに伸長する可能性があるためである.

すなわち,i_{0}\leq c'<i' を満たす全ての c' について,る.本アルゴリズムの流れを記す.Pals のすべて

Z

Z 形の接尾Z 形の縮約を行う.また,latransfer (c, i_{0}, i')における transfer にて既に計算した

j-1 までの Pals を多重に更新しなくてはならない場合がある.よって,RecManacher のアルゴリズムをそのまま両端ウォークからの最小線形鎖推論に用いると,時間計算量は 0(n^{2}) となる.

Algorithm 7: lamanacher(c, i)1i_{0}=i ;2i= laextension (c, i) ;3 if i<c then return i ;4i'= latransfer (c, i_{0}, i) ;3.3

LAmanacher アルゴリズム

5 if

両端ウォークからの最小線形鎖推論を 0(n) で計算する最適アルゴリズム LAmanacher を示す.本アルゴリズムは,観察2で示した,配列 Pals の要素を多重に更新しないように,Pals の要素を計算する前にc<i'<i then867 \lfo rgot '2;i=+1;Pal_{\mathcal{S}[\dot{i}']=

Pals [2*c-i'] ;9 return i' ;Z 形を先読みして検出し,縮約を行うアルゴリズムである.LAmanacher は,の終端位置が小さい順にw

中の Z 形Z 形の縮約を行い,最終の要素が-1となるように初期化する.ある i に対的に⑫を得る.アルゴリズム LAmanacher を Al‐

して, P_{\iota-1}(W_{k})=\{(j, Pals [j])|0\leq j<i-1\}であり, Z_{i-1}(w_{k})=\emptyset であると仮定する.Algo‐

gorithm 6に示す.また,Algorithm 6によって呼rithm 6の関数 LAmanacher(w) において,文字列のある位置について,Algorithm 7の関数

び出される関数 lamanacher(c, i) , laextension (c, i) ,w

latransfer (c, i_{0}, i'),lamanacheT (i-1, i) を呼び出し,lamanacher (i-1, i)skip(c, i) を,Algorithm 7—10

i-1

32
32

\overline{Algorithm8:laextension(c,i)}\overline{Algorithm10:skip(c,i)}1p=0 ;

1r=i-c-1;j=c-r ;2 whilew_{k}[i]=w_{k}[j] do846375 \ovalbalso[\xd{o\t{j}t-1]\gsemqrathlPalRs[i]E=PJals[jC-];T\l}foj=r_\{edtuont\{djo}t-{1j}-1;i;=^d+ellt;r(j=,\+do1t{;i});2 while Stack is not empty do

1r=i'-c-1;d=r ;109468573 \ovalbx{tsmalREJCT}|_{p=+1;^\dot{i}=S.ackp()P}\lfordt{i}=Sack.op()+r1;=\min^{C}Pals[c-d], Stak.op()]\};Stackop() C+\ita_{s[Scktop()]+1;}

2 while大回文 Pals [c] をRecManacher と同様にして求める.

if Pen9 Pals [c]=r ;10return i ;\overline{Algorithm9:latransfer(c,i_{0},i')}i_{0}\leq c+d do

1876543209 \ovbalsx[c'{]>r-dthe.nP,<=i1;f+\ovalbx{PetsmRE\JCT}[dfro_i]\dtone{{2q>i'hwt}Sau_ckps();}r2=lnm};ei,i|_'{d=-1^P,as[c'];\dthlS}==r;oi_{2|-fp\geqm,am+ntackush(x');}^P\l[]=rw{_{d1-\max,1,ie'-Gc,1\};19

return i' ;はAlgorithm 8の関数 laextension (i-1, i) を呼び出す.laextension (i-1, i) は,c=i-1 を中心とする極12

return i,p ;また,このとき,8行目の通りにPals [i] にPals [j-1]を代入する.これは,latransfer 関数で Pals を転写して求める前に,仮の Pals の値を計算する処理であり,仮転写と呼ぶ.仮転写された Pals の値は正しくない場合があるが,本アルゴリズムにおいては正当性を示すことができる.4行目の式において,形である

Z

xx^{R}x=w_{k}[j-r..i] が検出された場合を考える.ただし, |x|=r とする.このとき, w_{k} [j..i]を削除し, w_{k+1}=w_{k}[1..j-1]w_{k}[i+1..|w_{k}|] とし,j-1 を次の更新開始位置として return する.
Z形の縮約が起こらなかった場合,中心cの極大回文の半径 r が求まる.Algorithm 7 のlamanacher (i-1, i) の子関数である Algorithm 9の関数 latransfer (c, i_{0}=i, i'=c+r+1) において,i_{0}\leq c'\leq c+r の範囲で,降順に,極大回文 Pal_{\mathcal{S} [c]の左腕の情報を用いて Pals [c'] を求める.降順に転写を行い,再帰呼び出しを行うことが,実質的に Z形の先読みを行うことになる.

c' に対して,i' を次のように定義する.

i'= \max(\{j|j=RMostPal_{w_{k}}(c")
for some c'<c"\leq c+r })(1)

2行目の while ループ内において,常に i' が求まっ

33ている.また,関数 skip により,次を満たす i_{2} が返却されると仮定する.

i_{2}= \min(\{c'+r'+1|(c', r')\in P(w_{k})\}\cup\{i'\})(2)
各 c' と (c', r')\in P(w_{k}) を満たす r' に対して, c'+r'+1\geq i' となった場合を考える.このとき,16行目\frac{1\underline{C}r_{\neg}{:,\frac{1: !_{C_{2}:r^{ _2}:{1: 1 -}: .: :I!.\cdot:}:::\overline{Z_{c}(w_{k})=\emptyset}^{:}

図4: 補題1に矛盾する極大回文とZ 形との関係のように,Algorithm 7のlamanacher を引数 (c', i')によって再帰的に呼び出す.

lamanacher (c', i') の返り値ちが, i_{2}'>i' を満たすときを考える.アルゴリズムにおいて,関係 arrow=\{ (pxx^{R}xq, pxq) |x\in\Sigma^{+},p, q\in\Sigma^{*}\} によって Z 形が縮約され, w_{k}arrow^{*}w_{k'} となる w_{k'} が得られたとする.
このとき,次の while ループ変数 c'-r' に対しても,式1の i' は成立したままであり,補題2 (極大回文中の Z 形の存在条件 (2))(c, r)\in P(w_{k}) とする.

c<c'\leq c+r を満たす任意の c' について,(c', r')\in P(w_{k}) とし,式1におけZ_{c}(w_{k})=\emptyset かつ Z_{c',t'}(w_{k})=\emptyset\Rightarrow
任意の c2, r2について,{c2, r_{2}\rangle\in Z(w_{k}) ならばる i' を考える.

c_{2}+2r_{2}\geq i' である.

Z_{c'-\bullet',i^{J}}(w_{k'})=\emptyset
かつ P_{c-r',i^{\ovalbox{\tt\small REJECT}}}(w_{k'})=\{(j, Pals[j])|c'-r'<j<i'\}が言える.また, i_{2}' が, c\leq i_{2}'\leq i' を満たすときは,子もしくは孫の lamanacher において,Z 形の縮約が行われた場合である.この場合は,Algorithm 7のlamanacher における5行目から8行目に記述する処理に従う.

Algorithm

6のLAmanacherにおいて ,lamanacher(i — 1, i) の処理が終了して返り値i'が戻されたときを考える.このとき,

w_{k'}に対して,i'=RMostPal_{w_{k}}, (i-1) もしくは i'=i となる.このような i' に対して, Z_{i'}(w_{k'})=\emptyset かつP_{\iota'}(w_{k})=\{(j, Pals [j])|0\leq j<i'\} が成り立つ.
これを,w_{k}/[i-1]=\# となるまで繰り返すことで,\hat{w} が求まる.LAmanacher に関して,Z 形について次の補題が成立する.

補題1 (極大回文中の Z 形の存在条件 (1))(c, r)\in P(w_{k}) とする. Z_{c}(w_{k})=\emptyset\Rightarrow 任意の c_{2}, r_{2}について, \langle c_{2}, r_{2} } \in Z(w_{k}) ならば c_{2}+2r_{2}>c+rである.

補題1より,c+rZ 形\{c_{2}, r_{2}\rangle が存在するならば,必ずより大きい位置で終端するということが分かる.次の補題によって,すべての Z 形がLAmanacher\frac{1\vee\ell\prime:\lfloor r_{2}\vee:}{111:1}::\overline{Z_{C}(w_{k})=\emptyset}

Z_{c\prime.l}\overline{(w_{k})=}\emptyset:

図5: 補題2における,極大回文 (c, r) とループ変数

c', i' および Z 形 \{c_{2}, r_{2}\rangle との関係
また,仮転写された値に関して次の性質がある.

補題3 (仮転写された値の性質) P_{c}(w_{k})\{ (j, Pals [j]) 0 \leq j < c\} と仮定する.あるc, i について,laextension(c, i) によって,極大回文=(c, r) が求まり,0< á \leq rの範囲に対して,中心がc+d の仮転写された値を \overline{r}_{c+d} と書き,中心が c+dの極大回文の値を r_{c+d} と書く.任意の c+d\ovalbox{\t \small REJECT} こ対して次が成立する.

(1) d+\overline{r}_{c+d}<r\Rightarrow\overline{r}_{c+d}=r_{c+d},(2) \overline{r}_{c+d}\neq r_{c+d}\Rightarrow d+\overline{r}_{c+d}\geq r かつ d+r_{c+d}\geq r.の関数 laextenstion において検出されることが導か

補題3を用いて,LAmanacher の仮転写の正当性がれる.

次の補題で示される.

34
34が削除される.その後,(1) c'-r'=c なら,\frac{\underline{c}\underline{c+d}r}{\sim d_{: }\sim_{:!}\frac{1t\dot{:}\overline{r}_{c+d、} {I\backslash /}(1)

r_{c+d}:.

ある c2 \leq c に対して,laextension (c_{2}, c+1)がやり直される.また,(2) c'-r'>c なら,laextension (c, c'-r'+1) まで戻り,正当性を:保ったままアルゴリズムが再開される.

\frac{1 r\sear ow 1:\overline{r}_{c+d}: {I1\backslash _{:}\near ow^{I}

また,関数 skip に関して次の正当性が示される.

r_{c+d1}::(2)

P(w_{k}) とし,補題6 (skip の正当性) (c, r) \in
Z_{c-r,c}(w_{k})=\emptyset とする. c<c'\leq c+r の範囲の\vdash.

r_{c+d}

図6: 補題3における,仮転写された値 \overline{r}_{c+d} と正し
い極大回文の値 r_{c+d} との関係

補題4 (仮転写の正当性) P_{c}(w_{k})=\{ ( j , Pals [j] ) |0\leq j<c\} かつ灸 (w_{m})=\emptyset と仮定する.このとき,
íamanacheT (c, c+1) に対して laextension (c, c+1)c+が呼ばれ,極大回文 (c, r) が求まり, c+1,r の範囲に対して,Pals が仮転写されたとする.

任意の c' に対して,式1における i' を考える.いま,i'\neq c+r+1 であるとき,(c_{l}, r_{l})\in P(w_{k}),c_{l}<c_{l+1}\leq c_{l}+r_{l}<c_{l+1}+r_{l+1}, c_{1}=c'
このような列 c_{1} , c2,c_{q}latransfer (c, c+1, c+r+1) において, c<c'<c+r+1 の範囲の c' を考え, c' に対して式1にお:

\iota

:.

.p=3 c^{t\prime}r'-::\vdash_{c_{:}^{\mapsto i'}}.

立つ.

lamanacher (c, c+1)

lamanacher (c', i') を再る任意の仮転写された値は,参照した時点で正しい.
\bulletlamanacher (c, c + 1)

RMostPal_{w_{k}'}(c)の終了時,に対して ,P_{t'}(w_{k})i'\infty_{:}c_{1}\vdash\dotc_{2}plus_{:}-\dashv

ける i_{2} が返却されると仮定する.すると,次が成り帰呼び出しした際,lamanacher (c', i') が参照すに対して,グローバル:

ける i' を考える.また,関数 skip により,式2にお\bulletc_{q} および r_{q} を用いて i'=c_{q}+r_{q}+1 と書き, 1\leq l\leq q-1 に対して
c_{l}, r_{l} を以下に再帰的に定義する.

図7 補題6における,極大回文と関数 sk\iota p の返り値12, p との関係の例

図の関係においては, 1_{2}=i'および p=3 を返し,arrow’のとき,Stack は空である.

=な Stack に底から順に=ていると仮定する.このとき,文字列 w_{k} に対する\{ (j, Pals[j])|0\leq j<i'\} が成立する.
さらに,LAmanacher における Z 形の縮約の正当性を以下の補題によって示すことができる.

c_{q}, c_{q-1} ,, c_{1} が格納されsk_{i}p(c', c+r+1) は,式2における12および次を満たす p を 0(p) 時間で返す.
p は

sk_{i}p(c', c+r+1) において pop された回数.

ただし p は c_{p}+r_{p}<c'+r' を満たす最大の数
補題5 ( Z 形の縮約の正当性) (c, r) \in P(w_{k}) と\emptyset とする.ある c, i に対して 関数 sk_{i}p と Stack により,先読みによって Pals をし, Z_{c-r,c}(w_{k})laextension(c, i) が呼ばれ,極大回文 Pals [c]=r が 計算した範囲を多重に計算することがなくなる.
=求まったとする.

i<c'\leq c+r の範囲の任意の c' に対して,式1における i' を考えると,次が成り立つ.

. ある r' について, \langle c' — r', r' } \in Z(w_{k}) \Leftrightarrowlaextension (c', i') において w_{k}[c'-r'..c'+r']以上の補題によって,LAmanacher の正当性

計算量に関して次の定理を得る.

定理3 (LAmanacher の計算量) LAmanacher (w)は \hat{w} を 0(n) 時間領域で計算する.

35
参考文献
[1] J. A. Aslam and R. L. Rivest. Inferring graphsfrom walks. In Colt 19g\theta , pp. 359‐370, 1990.

[2] G. K. Manacher. A new linear‐time on‐line algo‐rithm for finding the smallest initial palindromeof a string. J. ACM, 22(3):346-351 , 1975.

[3] O. Maruyama and S. Miyano. Inferring a tree
from walks.

Theoretical Computer Science,

161(1):289-300 , 1996.

[4] V. Raghavan. Bounded degree graph inference
from walks. Journal of Computer and System

Sciences, 49(1):108‐ı32, 1994.