Алгоритми Манакер - Course 5
Алгоритми Манакер Алгоритми Манакер
Муқаддима
Алгоритми Манакер барои ёфтани зерпалиндромҳо дар сатри додашуда дар вақти хаттӣ истифода мешавад. Ба таври расмӣ, баёни масъала чунин аст: Сатре s s s бо дарозии n n n дода шудааст. Ҳамаи ҷуфтҳои ( i , j ) (i, j) ( i , j ) -ро ёбед, ки зерсатри s [ i … j ] s[i\dots j] s [ i … j ] палиндром бошад. Сатри t t t палиндром аст, вақте ки ( сатри баръаксшудаи аст).
t = t r e v t = t_{rev} t = t re v
Алгоритм
Равиши содда Ҳалли мустақим метавонад аз гузаштан аз ҳар як аломати сатри додашуда ва баррасӣ кардани он ҳамчун маркази палиндром иборат бошад, яъне ба аломатҳои ҳамсоя нигоҳ карда, мавқеъҳоро то ҳадде ки имконпазир аст зиёд кардан, ва ҳар дафъа як ҷуфти аломатҳои мувофиқро муқоиса кардан. Барои пешгирӣ аз overflow ва гузаштан аз сарҳадҳои чап ва рост, метавон аломатҳои терминалӣ илова кард, то он сарҳадҳоро нишон диҳанд.
Татбиқи алгоритми содда чунин аст:
Аломатҳои терминалии $ ва ^ истифода шуданд, то бо охирҳои сатр ҷудогона сарукор надошта бошем.
Алгоритми Манакер барои сатри дарозии тоқ Бигзор d o d d [ i ] d_{odd}[i] d o dd [ i ] палиндромҳои дарозии тоқро, ки марказашон дар i i i аст, нишон диҳад. Бигзор ( l , r ) (l, r) ( l , r ) сарҳадҳои росттарин (зер-)палиндроми ёфтшуда бошанд (яъне росттарин (зер-)палиндроми ҷорӣ s [ l + 1 ] s [ l + 2 ] … s [ r − 1 ] s[l+1] s[l+2] \dots s[r-1] s [ l + 1 ] s [ l + 2 ] … s [ r − 1 ] аст). Дар оғоз, l = 0 , r = 1 l = 0, r = 1 l = 0 , r = 1 , ки сатри холӣ мебошад.
Баъд, мо мехоҳем d o d d [ i ] d_{odd}[i] d o dd [ i ] -ро ҳисоб кунем, пас:
Агар i i i берун аз зерпалиндроми ҷорӣ бошад, яъне i ≥ r i \geq r i ≥ r , мо метавонем равиши соддаи дар боло тавсифшударо истифода барем.
Агар i ≤ r i \le r i ≤ r , биёед мавқеи "оина"-и i i i -ро дар зерпалиндроми ( l , r ) (l, r) ( l , r ) ёбем, яъне мавқеи j = l + ( r − i ) j = l + (r - i) j = l + ( r − i ) -ро мегирем, ва қимати
d o d d [ j ] d_{odd}[j] d o dd [ j ] -ро месанҷем. Азбаски j j j мавқеи симметрии i i i нисбат ба ( l + r ) / 2 (l+r)/2 ( l + r ) /2 аст, мо қариб ҳамеша метавонем d o d d [ i ] = d o d d [ j ] d_{odd}[i] = d_{odd}[j] d o dd [ i ] = d o dd [ j ] таъин кунем. Тасвири ин (палиндроми атрофи
j j j воқеан ба палиндроми атрофи
i i i "нусха" мешавад):
… s l + 1 … s j − d o d d [ j ] + 1 … s j … s j + d o d d [ j ] − 1 ⏟ palindrome … s i − d o d d [ j ] + 1 … s i … s i + d o d d [ j ] − 1 ⏟ palindrome … s r − 1 ⏞ palindrome … \ldots\ \overbrace{ s_{l+1}\ \ldots\ \underbrace{ s_{j-d_{odd}[j]+1}\ \ldots\ s_j\ \ldots\ s_{j+d_{odd}[j]-1}\ }_\text{palindrome}\ \ldots\ \underbrace{ s_{i-d_{odd}[j]+1}\ \ldots\ s_i\ \ldots\ s_{i+d_{odd}[j]-1}\ }_\text{palindrome}\ \ldots\ s_{r-1}\ }^\text{palindrome}\ \ldots …
Ҳолати ҳиллагарона метавонад он бошад, ки палиндроми "дарунӣ" ба сарҳадҳои "берунӣ" мерасад, яъне
j − d o d d [ j ] ≤ l j - d_{odd}[j] \le l j − d o dd [ j ] ≤ l (ё, ки ҳамон аст,
i + d o d d [ j ] ≥ r i + d_{odd}[j] \ge r i + d o dd [ j ] ≥ r ). Азбаски симметрия берун аз палиндроми "берунӣ" кафолат дода намешавад, танҳо таъин кардани
d o d d [ i ] = d o d d [ j ] d_{odd}[i] = d_{odd}[j] d o dd [ i ] = d o dd [ j ] нодуруст хоҳад буд: мо маълумоти кофӣ надорем, то бигӯем, ки палиндром дар мавқеи
i i i ҳамон дарозиро дорад.
Барои дуруст коркард кардани чунин ҳолатҳо, мо бояд дарозии палиндромро ҳоло маҳдуд кунем, яъне d o d d [ i ] = r − i d_{odd}[i] = r - i d o dd [ i ] = r − i , . Баъд аз ин мо равиши соддаи дар боло тавсифшударо иҷро мекунем, ки кӯшиш мекунад
d o d d [ i ] d_{odd}[i] d o dd [ i ] -ро то ҳадде ки имконпазир аст зиёд кунад.
Тасвири ин ҳолат (палиндром бо маркази
j j j маҳдуд карда мешавад, то ба палиндроми "берунӣ" мувофиқат кунад):
… s l + 1 … s j … s j + ( j − l ) − 1 ⏟ palindrome … s i − ( r − i ) + 1 … s i … s r − 1 ⏟ palindrome ⏞ palindrome … … … … … ⏟ try moving here \ldots\ \overbrace{ \underbrace{ s_{l+1}\ \ldots\ s_j\ \ldots\ s_{j+(j-l)-1}\ }_\text{palindrome}\ \ldots\ \underbrace{ s_{i-(r-i)+1}\ \ldots\ s_i\ \ldots\ s_{r-1} }_\text{palindrome}\ }^\text{palindrome}\ \underbrace{ \ldots \ldots \ldots \ldots \ldots }_\text{try moving here} … palindrome s l + 1 … s j … palindrome s i − ( r − i ) + 1 … palindrome try moving here ……………
Дар тасвир нишон дода шудааст, ки гарчанде палиндром бо маркази
j j j метавонад калонтар бошад ва берун аз палиндроми "берунӣ" равад, аммо бо
i i i ҳамчун марказ мо метавонем танҳо он қисмеро истифода барем, ки пурра ба палиндроми "берунӣ" ҷой мегирад. Аммо ҷавоб барои мавқеи
i i i (
d o d d [ i ] d_{odd}[i] d o dd [ i ] ) метавонад аз ин қисм хеле калонтар бошад, бинобар ин баъд мо алгоритми соддаи худро иҷро мекунем, ки кӯшиш мекунад онро берун аз палиндроми "берунӣ" калон кунад, яъне ба минтақаи "try moving here". Ёдовар мешавем, барои дуруст кор кардан мо бояд қиматҳои ( l , r ) (l, r) ( l , r ) -ро баъд аз ҳисоб кардани ҳар як d o d d [ i ] d_{odd}[i] d o dd [ i ] нав кунем.
Татбиқ барои алгоритми Манакер бо дарозии тоқ:
Алгоритми Манакер барои ҳолати умумӣ Гарчанде мо метавонистем равиши болоиро истифода барем ва онро тағйир диҳем, то ду аломатро ҳамчун марказҳои сатри дарозии ҷуфт баррасӣ кунем, мумкин аст тамоми масъаларо ба ҳолате кам кунем, ки мо танҳо бо палиндромҳои дарозии тоқ сарукор дорем. Барои ин, мо метавонем як аломати иловагии # \# # -ро байни ҳар як ҳарф дар сатр ва инчунин дар оғоз ва охири сатр гузорем. Ин ҳамоно хосиятҳои палиндромҳои мавҷударо нигоҳ медорад ва сатрро дарозии тоқ мекунад:
a b c b c b a → # a # b # c # b # c # b # a # , abcbcba \to \#a\#b\#c\#b\#c\#b\#a\#, ab c b c ba → # a # b # c # b # c # b # a # ,
d = [ 1 , 2 , 1 , 2 , 1 , 4 , 1 , 8 , 1 , 4 , 1 , 2 , 1 , 2 , 1 ] . d = [1,2,1,2,1,4,1,8,1,4,1,2,1,2,1]. d = [ 1 , 2 , 1 , 2 , 1 , 4 , 1 , 8 , 1 , 4 , 1 , 2 , 1 , 2 , 1 ] .
Дар ин ҷо, d [ 2 i ] = 2 d e v e n [ i ] + 1 d[2i]=2 d_{even}[i]+1 d [ 2 i ] = 2 d e v e n [ i ] + 1 ва d [ 2 i + 1 ] = 2 d o d d [ i ] d[2i+1]=2 d_{odd}[i] d [ 2 i + 1 ] = 2 d o dd [ i ] ки дар он d d d массиви Манакерро барои палиндромҳои дарозии тоқ дар сатри бо # \# # -пайвастшуда нишон медиҳад, дар ҳоле ки d o d d d_{odd} d o dd ва d e v e n d_{even} d e v e n ба массивҳои дар боло муайяншуда дар сатри ибтидоӣ мувофиқат мекунанд.
Алгоритм бо танзими сатр метавонад чунин татбиқ шавад:
s l + 1 … palindrome s j − d o dd [ j ] + 1 … s j … s j + … palindrome s i − d o dd … s r − 1 palindrome
…
…
s j + ( j − l ) − 1
s i
…
s r − 1
vector < int > simpleManacher ( string s ) {
int n = s . size ( ) ;
s = "$" + s + "^" ;
vector < int > p ( n + 2 ) ;
for ( int i = 1 ; i < = n ; i ++ ) {
while ( s [ i - p [ i ] ] == s [ i + p [ i ] ] ) {
p [ i ] ++ ;
}
}
return vector < int > ( begin ( p ) + 1 , end ( p ) - 1 ) ;
}
vector < int > oddLengthManacher ( string s ) {
int n = s . size ( ) ;
s = "$" + s + "^" ;
vector < int > p ( n + 2 ) ;
int l = 1 , r = 1 ;
for ( int i = 1 ; i < = n ; i ++ ) {
p [ i ] = max ( 0 , min ( r - i , p [ l + ( r - i ) ] ) ) ;
while ( s [ i - p [ i ] ] == s [ i + p [ i ] ] ) {
p [ i ] ++ ;
}
if ( i + p [ i ] > r ) {
l = i - p [ i ] , r = i + p [ i ] ;
}
}
return vector < int > ( begin ( p ) + 1 , end ( p ) - 1 ) ;
}
vector < int > adjustedManacher ( string s ) {
string t ;
for ( auto c : s ) {
t += string ( "#" ) + c ;
}
auto res = oddLengthManacher ( t + "#" ) ;
return vector < int > ( begin ( res ) + 1 , end ( res ) - 1 ) ;
}
d
o dd
[
j
]
−
1
[
j
]
+
1
…
s i
…
s i + d o dd [ j ] − 1