297
правок
Изменения
Нет описания правки
|align="left" colspan="4"|
<font size=2>
tm[0...n - m][1...k + 1] = m + 1 <font color=green> // инициализация</font>
r = 0
j = 0
'''for ''' i = 0 to n - m
b = 0
'''if ''' i < j
b = merge(i, r, j)
'''if ''' b < k + 1
r = i
extend(i, j, b)
<font size=2>
extend(i, j, b)
'''while ''' (b < k + 1) '''and ''' (j - i < m)
j++
'''if ''' y[j] != <tex>\neq</tex> x[j-1]
b++
tm[i][b] = j - i
u = 1
v = q
'''while ''' (b < k + 1) '''and ''' (v < k + 2) '''and ''' (i + pm[i - r][u] < j '''or ''' tm[r][v] != <tex>\neq</tex> m + 1) '''if ''' i + pm[i - r][u] > r + tm[r][v] <font color=green> // Случай 2, условие A</font>
b++
tm[i][b] = tm[r][v] - (i - r)
v++
'''else ''' '''if ''' i + pm[i - r][u] < r + tm[r][v] <font color=green> // Случай 2, условие B</font>
b++
tm[i][b] = pm[i - r][u]
u++
'''else ''' '''if ''' i + pm[i - r][u] = r + tm[r][v] <font color=green> // Случай 3 </font> '''if ''' x[pm[i - r][u]] != <tex>\neq</tex> y[i + pm[i - r][u]]
b++
tm[i][b] = pm[i - r][u]
r = <tex>2^{s-1}</tex>
j = <tex>2^{s-1}</tex>
'''for ''' i = <tex>2^{s-1}</tex> to <tex>2^{s} - 1</tex>
b = 0
'''if ''' i < j
merge(i, r, j, b)
'''if ''' b < min{<tex>2^{\log(m-1)}2k - 1, m - 2^{s} </tex>}
r = i
extend(i, j, b)
