74
правки
Изменения
→Псевдокод
==Псевдокод==
'''function''' twoWaySearch(String pattern, String text):
n = pattern.length
<tex>\langle</tex>len1, p1<tex>\rangle</tex> <tex>\leftarrow</tex> maxSuffix(pattern, <tex>\leqslant</tex>)
<tex>\langle</tex>len2, p2<tex>\rangle</tex> <tex>\leftarrow</tex> maxSuffix(pattern, <tex>\geqslant</tex>)
'''if''' len1 <tex>\geqslant</tex> len2:
len = len1
p = p1
'''else''':
len = len2
p = p2
occurences = <tex>\varnothing</tex>
pos <tex>\leftarrow</tex> 0
memPrefix <tex>\leftarrow</tex> 0
'''if''' len < n/2 '''and''' pattern[1<tex>\ldots</tex>len] <tex>-</tex> суффикс pattern[len + 1<tex>\ldots</tex>len + p]:
'''while''' pos + n <tex>\leqslant</tex> text.length:
i <tex>\leftarrow \max</tex>(l, memPrefix) + 1
'''while''' i <tex>\leqslant</tex> n '''and''' pattern[i] <tex>=</tex> text[pos + i]:
i++
'''if''' i <tex>\leqslant</tex> n:
pos <tex>\leftarrow</tex> pos + <tex>\max</tex>(i <tex>-</tex> len, memPrefix <tex>-</tex> p <tex>+</tex> 1)
memPrefix <tex>\leftarrow</tex> 0
'''else''':
j <tex>\leftarrow</tex> l
'''while''' j <tex> > </tex> memPrefix '''and''' pattern[j] <tex>=</tex> text[pos + j]:
j--
'''if''' j <tex>\leqslant</tex> memPrefix:
pos <tex>\rightarrow</tex> occurences
pos <tex>\leftarrow</tex> pos <tex>+</tex> p
memPrefix <tex>\leftarrow</tex> n <tex>-</tex> p
'''else''':
q <tex>\leftarrow \max</tex>(len, n <tex>-</tex> len) <tex>+</tex> 1
'''while''' pos + n <tex>\leqslant</tex> text.length:
i <tex>\leftarrow</tex> len + 1
'''while''' i <tex>\leqslant</tex> n '''and''' pattern[i] <tex>=</tex> text[pos <tex>+</tex> i]:
i++
'''if''' i <tex>\leqslant</tex> n:
pos <tex>\leftarrow</tex> pos <tex>+</tex> i <tex>-</tex> len
'''else''':
j <tex>\leftarrow</tex> len
'''while''' j <tex> > </tex> 0 '''and''' pattern[j] <tex>=</tex> text[pos <tex>+</tex> j]:
j--
'''if''' j <tex>=</tex> 0:
pos <tex>\rightarrow</tex> occurences
pos <tex>\leftarrow</tex> pos <tex>+</tex> q
'''return''' occurences
