271
правка
Изменения
→Разбор случаев
Условные обозначения:
* 1. Черная вертикальная линия на рисунке обозначает <tex> lcp </tex> от <tex> i </tex>-го суффикса суффиксного массива <tex> array </tex> и образца <tex> p </tex>. Чем линия длиннее, тем совпадений символов больше. * 2. L, M и R - то же самое, что в алгоритме. Кроме того, самая левая черная вертикальная линия на каждом рисунке означает <tex> l </tex>, аналогично, самая правая черная вертикальная линия на каждом рисунке означает <tex> r </tex>. Переменная <tex> m_l </tex> - это <tex> lcp </tex> в суффиксном массиве на промежутке <tex> [L, M] </tex>. Переменная <tex> m_r </tex> - это <tex> lcp </tex> в суффиксном массиве на промежутке <tex> [M, R] </tex>.
* 3. Серым цветом выделен <tex> lcp </tex> в суффиксном массиве на рассматриваемом промежутке.
Простой пример для образца <code> aaa </code> на отсортированных суффиксах строки <code> aaaaaa </code>.
Жирным выделены буквы, которые на рисунках будут представлены черными линиями (совпадения с образцом), а серым {{---}} совпадения суффиксов друг с другом на промежутке <tex> [LM, MR] </tex>.
[[Файл:examp2examp3.png]]
Дальнейший разбор случаев никак не связан со строкой <code> aaaaaa </code> и образцом <code> aaa </code>. <br>
[[Файл:left.png]]
* a) <tex> l < m_l </tex>. Сдвигаем <tex> L </tex> в <tex> M </tex>. Значение <tex> l </tex> не изменяется.
* b) <tex> l = m_l </tex>. Считаем <tex> lcp </tex> для образца и суффикса в позиции <tex> M </tex> с позиции <tex> l </tex>.
* с) <tex> l > m_l </tex>. Сдвигаем <tex> R </tex> в <tex> M </tex>, <tex> r = m_l </tex>.
[[Файл:right2.png]]
* a) <tex> r < m_r </tex>. Сдвигаем <tex> R </tex> в <tex> M </tex>. Значение <tex> r </tex> не изменяется.
* b) <tex> r = m_r </tex>. Считаем <tex> lcp </tex> для образца и суффикса в позиции <tex> M </tex> с позиции <tex> r </tex>.
* с) <tex> r > m_r </tex>. Сдвигаем <tex> L </tex> в <tex> M </tex>, <tex> l = m_r </tex>.
