Как работает этот код для получения LCP из суффиксного массива?
Может кто-нибудь объяснить, как работает этот код для построения LCP из суффиксного массива? suffixArr[] массив такой, что suffixArr[i] содержит значение индекса в строке для суффикса с рангом я.
void LCPconstruct()
{
int i,C[1001],l;
C[suffixArr[0]] = n;for(i=1;i<n;i++)
C[suffixArr[i]] = suffixArr[i-1];
l = 0;
for(i=0;i<n;i++)
{
if(C[i]==n)
LCPadj[i] = 0;
else
{
while(i+l<n && C[i]+l<n && s[i+l] == s[C[i]+l])
l++;
LCPadj[i] = l;
l = max(l-1,0);
}
}
for(i=0;i<n;i++)
cout<<LCPadj[suffixArr[i]]<<"\n";}
Решение
Во-первых, важно понимать, что алгоритм обрабатывает суффиксы в исходном порядке, то есть в том порядке, в котором они появляются во входной строке. Не в лексикографическом порядке.
Так что, если входная строка abxabcсначала учитывает abxabc, затем bxabc, затем xabc и так далее.
Для каждого суффикса, который он рассматривает в этом порядке, он определяет позицию суффикса, который является его лексикографическим предшественником.(*) (поэтому здесь и только здесь используется понятие лексикографического порядка). Для первого суффикса abxabcлексикографическим предшественником, то есть суффиксом, который появляется непосредственно перед ним в лексикографическом порядке суффиксов, является abc, Это определяется с помощью поиска O (1) в массиве. C, который был подготовлен специально для этой цели.
Внутренний цикл сравнивает символы abxabc а также abc один за другим и определяет, что эти два суффикса имеют первые 2 общих символа. Это переменная l в вашем коде, а это значит, что запись в LCP для суффикса abxabc должно быть 2, поэтому мы устанавливаем LCPadj[i] = l, Обратите внимание, что i здесь относится к позиции суффикса во входной строке, а не к его позиции в массиве суффиксов. Так LCPadj это не массив LCP (пока). Это вспомогательная структура данных.
Затем он переходит к следующей строке, которая bxabc, Опять же он использует C чтобы найти это bc является лексикографическим предшественником этого, а затем определяет, сколько префиксных символов разделяют два. И тут возникает хитрость: можно быть уверенным, что это должно быть по крайней мере столько же, сколько на предыдущем шаге (т.е. 2), минус 1. Почему? Потому что строка, которую мы сейчас рассматриваем, bxabc, это, конечно, суффикс ранее рассмотренной строки (abxabc), следовательно, лексикографический предшественник этой строки (abc) также должен иметь суффикс, который на 1 символ короче (bc), и этот суффикс также должен быть где-то в массиве суффиксов, и он должен разделять свой префикс с рассматриваемой в данный момент строкой, за исключением первого символа. Более того, не может быть другого суффикса, который был бы более коротким и лексикографически ближе к рассматриваемой в настоящее время строке. Последнее вполне логично, если подумать о том, как работает лексикографическая сортировка, но есть и формальные доказательства этого (например, лемма 5.10 в лекции Кярккяйнена Вот)
Так что это описывает основной принцип работы здесь. Есть несколько вещей, которые следует отметить в вашем коде, чтобы полностью понять роль каждой переменной:
- Как объяснили,
Cвспомогательный массив (nцелые числа в длину), которая хранит для каждого суффикса во входной строке положение этого другого суффикса, который является его непосредственным лексикографическим предшественником. Этот массив создается не слева направо, а (разумно), проходя через массив суффиксов слева направо, поскольку это позволяет легко определить непосредственный лексикографический предшественник любой строки: непосредственный лексикографический предшественник суффикса, начинающийся с позицииsuffixArr[i]конечно, должен быть расположен в положенииsuffixArr[i-1], Подтвердите в своем коде, что это какCопределено. - Как уже упоминалось выше,
LCPadjхранит значения LCP для суффикса в порядке их появления во входной строке, а не в том порядке, в котором они появляются в массиве суффиксов. Вот почему во время вывода,LCPadjпечатается не слева направо, а через массив суффиксов слева направо и печатьLCPadj[i]в этой последовательности. Подтвердите, что это так.
Надеюсь, это поможет. Дайте мне знать, если нет.
(*)От лексикографический предшественник Я имею в виду немедленный предшественник суффикса в лексикографически упорядоченном списке суффиксов, то есть суффикс к его непосредственному левому краю в массиве суффиксов.
Другие решения