3622
правки
Изменения
м
→Псевдокод
==Псевдокод==
'''function''' twoWaySearch('''String''' pattern, '''String''' text): '''vector <int>'''
<font color=green>//предобработка <tex>-</tex> вычисление критической позиции (в которой строка делится на <tex>u</tex> и <tex>v</tex>)</font>
<tex>\langle</tex>l1, p1<tex>\rangle</tex> = maxSuffix(pattern, <tex>\leqslant</tex>)
<tex>\langle</tex>l, p<tex>\rangle</tex> = l1 <tex>\geqslant</tex> l2 ? <tex>\langle</tex>l1, p1<tex>\rangle</tex> : <tex>\langle</tex>l2, p2<tex>\rangle</tex>
<font color=green>//<tex>p</tex> <tex>-</tex> период <tex>x</tex>, <tex>l</tex> <tex>-</tex> такая критическая позиция, что <tex>l<p</tex></font>
'''vector <int> ''' occurences <font color=green>// набор всех вхождений образца в текст</font>
'''int''' pos = 0
'''int''' memPrefix = 0
j--
'''if''' j <tex>\leqslant</tex> memPrefix
occurences.push_backpushBack(pos)
pos = pos + p
memPrefix = pattern.length - p
