Может кто-нибудь объяснить, как работает этот код для построения 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]
в этой последовательности. Подтвердите, что это так.Надеюсь, это поможет. Дайте мне знать, если нет.
(*)От лексикографический предшественник Я имею в виду немедленный предшественник суффикса в лексикографически упорядоченном списке суффиксов, то есть суффикс к его непосредственному левому краю в массиве суффиксов.