Объяснение алгоритма минимального циклического сдвига

Question

Я недавно столкнулся с этим кодом без каких-либо комментариев. Он находит минимальный циклический сдвиг слова (этот код специально возвращает его индекс в строке) и его называют алгоритмом Дюваля. Только info , который я нашел, описывает алгоритм в нескольких словах и имеет более чистый код. Буду признателен за любую помощь в понимании этого алгоритма. Я всегда находил текстовые алгоритмы довольно хитрыми и довольно сложными для понимания.

int minLexCyc(const char *x) {
    int i = 0, j = 1, k = 1, p = 1, a, b, l = strlen(x);
    while(j+k <= (l<<1)) {
        if ((a=x[(i+k-1)%l])>(b=x[(j+k-1)%l])) {
            i=j++;
            k=p=1;
        } else if (a<b) {
            j+=k; 
            k=1; 
            p=j-i;
        } else if (a==b && k!=p) {
            k++;
        } else {
            j+=p; 
            k=1;
        }
    }
    return i;
}

Answer 1

Во-первых, я считаю, что в вашем коде есть ошибка. Последняя строка должна быть return p;. Я считаю, что у меня есть индекс лексикографически наименьшего циклического сдвига, а р - наименьший соответствующий сдвиг. Я также думаю, что ваше условие остановки слишком слабое, то есть вы слишком много проверяете после того, как нашли совпадение, но я точно не знаю, каким оно должно быть.

Обратите внимание, что i и j только продвигаются и что i всегда меньше j. Мы ищем строку, которая соответствует строке, начинающейся с i, и пытаемся сопоставить ее со строкой, начинающейся с j. Мы делаем это путем сравнения k-го символа каждой строки при увеличении k (до тех пор, пока они совпадают). Обратите внимание, что мы меняем i, только если определяем, что строка, начинающаяся с j, лексикографически меньше, чем строка, начинающаяся с j, а затем мы устанавливаем i в j и сбрасываем k и p в их начальные значения.

У меня нет времени на подробный анализ, но, похоже,

1. i = начало лексикографического наименьшего циклического сдвига
2. j = начало циклического сдвига, который мы сопоставляем со сдвигом, начинающимся в i
3. k = символ в строках i и j, которые в данный момент находятся на рассмотрении (строки соответствуют позициям от 1 до k-1
4. p = рассматриваемый циклический сдвиг (я верю, что p обозначает префикс)

Редактировать Идем дальше

этот раздел кода

    if ((a=x[(i+k-1)%l])>(b=x[(j+k-1)%l])) {
        i=j++;
        k=p=1;

Перемещает начало сравнения в лексикографически более раннюю строку, когда мы ее находим, и повторно инициализирует все остальное.

этот раздел

   } else if (a<b) {
        j+=k; 
        k=1; 
        p=j-i;

это сложная часть. Мы обнаружили несоответствие, которое лексикографически позже, чем наша справочная строка, поэтому мы переходим к концу сопоставленного текста и начинаем сопоставление оттуда. Мы также увеличиваем p (наш шаг). Почему мы можем пропустить все начальные точки между j и j + k? Это потому, что строка, начинающаяся с i, является лексикографически наименьшей из видимых, и если хвост текущей j-строки больше, чем строка в i, тогда любой суффикс строки в j будет больше, чем строка в i.

Наконец

    } else if (a==b && k!=p) {
        k++;
    } else {
        j+=p; 
        k=1;

это просто проверяет, что строка длины p, начиная с i, повторяется.

** дальнейшее редактирование * Мы делаем это, увеличивая k до k == p, проверяя, что k-й символ строки, начинающейся с i, равен k-му символу строки, начинающейся с j. Как только k достигает p, мы снова начинаем сканирование при следующем предполагаемом вхождении строки.

Еще больше отредактируйте , чтобы попытаться ответить на вопросы Джетро.

Первое: k != p в else if (a==b && k!=p) Здесь мы имеем совпадение в том, что k-й и все предыдущие символы в строках, начинающихся с i и j, равны. Переменная p представляет длину, которую мы считаем повторяющейся строкой. Когда k != p, на самом деле k < p, поэтому мы гарантируем, что p символов в строке, начинающейся в i, совпадают с p символами в строке, начинающейся в j. Когда k == p (последнее), мы должны быть в точке, где строка, начинающаяся с j + k, выглядит так же, как строка, начинающаяся с j, поэтому мы увеличиваем j на p и устанавливаем k обратно в 1 и возвращаемся к сравнению две строки.

Второе: да, я верю, что вы правы, он должен вернуть меня. Я неправильно понял значение «минимального циклического сдвига»

Answer 2

Может быть таким же, как этот алгоритм, объяснение которого можно найти здесь :

int ComputeMaxSufPos(string w)
{
    int i = 0, n = w.Length;
    for (int j = 1; j < n; ++j)
    {
        int c, k = 0;
        while ((c = w[(i + k) % n].CompareTo(w[(j + k) % n])) == 0 && k != n)
        { k++; }
        j += c > 0 ? k / (j - i) * (j - i) : k;
        i = c > 0 ? j : i;
    }
    return i;
}