Как работает этот код для получения LCP из массива суффиксов?

Может кто-нибудь объяснить, как работает этот код для построения LCP из массива суффиксов? suffixArr[] — это массив, в котором suffixArr[i] содержит значение индекса в строке для суффикса с рангом 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";


}

c++ algorithm suffix-array
person Dhruv Mullick    schedule 17.10.2014    source источник
comment
Ну откуда ты это взял?   -  person Lightness Races in Orbit    schedule 17.10.2014
comment
Я просматривал решение вопроса на codechef. codechef.com/problems/MOU1H   -  person Dhruv Mullick    schedule 17.10.2014
comment
А длинная редакция решения не помогла понять, как это работает? Это довольно подробно.   -  person Lightness Races in Orbit    schedule 17.10.2014
comment
На самом деле я видел код пользователя, так как мой метод создания массива суффиксов наиболее близок к его. Метод, используемый в редакции, совершенно другой.   -  person Dhruv Mullick    schedule 17.10.2014
comment
Я не уверен, как мы использовали l здесь. Он обновляется до max(l-1,0) после каждой итерации, а не с 0 каждый раз.   -  person Dhruv Mullick    schedule 17.10.2014

Ответы (1)


arrow_upward
8
arrow_downward

Во-первых, важно понимать, что алгоритм обрабатывает суффиксы в исходном порядке, то есть в том порядке, в котором они появляются во входной строке. Не в лексикографическом порядке.

Таким образом, если входная строка 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] в этом порядке. Подтвердите, что это так.

Надеюсь, это поможет. Дайте мне знать, если нет.

(*)Под лексикографическим предшественником я подразумеваю непосредственный предшественник суффикса в лексикографически упорядоченном списке суффиксов, т. е. суффикс непосредственно слева от него. в массиве суффиксов.

person jogojapan    schedule 18.10.2014