Изменения

Алгоритм поиска подстроки в строке с помощью суффиксного массива

68 байт добавлено, 11:45, 7 июня 2011

→‎Разбор случаев

* 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>.

* 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>.

271

правка