Изменения

Декомпозиция Линдона

108 байт добавлено, 12:44, 3 мая 2014

→‎Реализация

===Реализация===

'''string ''' s <font color=green> // входная строка</font> '''string[] ''' words <font color=green> // декомпозиция</font>

n <tex>\leftarrow</tex> |s|

i <tex>\leftarrow</tex> 0

w cur <tex>\leftarrow</tex> 0 '''while''' i < n {: j <tex>\leftarrow</tex> i + 1

k <tex>\leftarrow</tex> i

'''while''' j < tex> < </tex> n '''and''' s[k] <= tex> \leqslant </tex> s[j] {: '''if''' s[k] < tex> < </tex> s[j]:

k <tex>\leftarrow</tex> i

'''else:'''

k <tex>\leftarrow</tex> k + 1

j <tex>\leftarrow</tex> j + 1

} '''while''' i <tex>\leqslant</tex> k {: words[wcur] <tex>\leftarrow</tex> s[i..j-k] w cur <tex>\leftarrow</tex> w + 1

i <tex>\leftarrow</tex> i + j - k;

}

===Корректность===

3622

правки