Самая длинная общая подстрока в реализации 2 строк

Question

Я пытаюсь реализовать самый длинный алгоритм общих подстрок в C, и после прочтения поста ниже, я действительно запутался в следующей части:

Теперь самое большое значение LCP[2]=3, но оно для SA[1] и SA[2], оба из которых начинаются со строки A. Итак, мы игнорируем это. С другой стороны, LCP[4]=2 для SA[3] (соответствует суффиксу bc в B) и SA[4] (соответствует суффиксу bcabC# bc в A). Итак, это самая длинная распространенная подстрока.

Мой результат LCP также отличается от приведенного примера.

https://cs.stackexchange.com/questions/9555/computing-the-longest-common-substring-of-two-strings-using-suffix-arrays

строка A = abcabc

строка B = bc

разделитель строк: '#'

Суффиксный массив

[#bc, abC# bc, abcabC# bc, bc, bC# bc, bcabC# bc, c, C# bc, cabC# bc]

LCP

[-1, 0, 3, 0, 2, 2, 0, 1, 1]

ИЛИ удаляя первый элемент

Суффиксный массив

[abC# bc, abcabC# bc, bc, bC# bc, bcabC# bc, c, C# bc, cabC# bc]

LCP

[0, 3, 0, 2, 2, 0, 1, 1]

Я вижу, что SA [3] соответствует bc, но SA [4] соответствует (я полагаю) #bcbc. Вот что меня смущает.

Кто-нибудь может уточнить по этому поводу? Спасибо!

Answer 1

Я вижу, что SA[3] соответствует bc, но SA[4] соответствует (я полагаю) #bcbc.

Там нет #bcbc, чтобы найти где-либо выше. Цитата говорит "SA[4] (соответствует суффиксу bcabC#bc of A)", и это, безусловно, верно:

 0       1          2   3      4         5  6     7        index
[abc#bc, abcabc#bc, bc, bc#bc, bcabc#bc, c, c#bc, cabc#bc] Suffix Array
[0,      3,         0,  2,     2,        0, 1,    1]       LCP

SA [2] - это суффикс B, а SA[3] - это суффикс A(#B), поэтому самая длинная общая подстрока - это bc длины 2.