Объяснение алгоритма минимального циклического сдвига
Недавно я столкнулся с этим кодом без каких-либо комментариев. Он находит минимальный циклический сдвиг слова (этот код специально возвращает его индекс в строке) и его называют алгоритмом Дюваля. Только 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 (a1 ответ
Во-первых, я считаю, что в вашем коде есть ошибка. Последняя строка должна быть такой.
return p;. Я полагаю, что i содержит индекс лексикографически наименьшего циклического сдвига, а p содержит наименьший сдвиг, который совпадает. Я также думаю, что ваше условие остановки слишком слабое, т.е. вы делаете слишком много проверок после того, как нашли совпадение, но я не уверен, каким именно оно должно быть.
Обратите внимание, что i и j только прогрессируют, и что i всегда меньше j. Мы ищем строку, которая совпадает со строкой, начинающейся на i, и пытаемся сопоставить ее со строкой, начинающейся на j. Мы делаем это, сравнивая k-й символ каждой строки, увеличивая k (до тех пор, пока они совпадают). Обратите внимание, что мы меняем i, только если определим, что строка, начинающаяся на j, лексикографически меньше строки, начинающейся на j, и тогда мы устанавливаем i на j и возвращаем k и p к их начальным значениям.
У меня нет времени на подробный анализ, но выглядит это так
- i = начало лексикографически наименьшего циклического сдвига
- j = начало циклического сдвига, который мы сопоставляем со сдвигом, начинающимся на i
- k = символ в строках i и j, рассматриваемых в данный момент (строки совпадают в позициях с 1 по k-. 1
- p = рассматриваемый циклический сдвиг (я полагаю, что p означает префикс)
Edit Идем дальше
этот раздел кода
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 (последнее else), мы должны оказаться в точке, где строка, начинающаяся на j + k, выглядит так же, как и строка, начинающаяся на j, поэтому мы увеличиваем j на p, устанавливаем k обратно в 1 и возвращаемся к сравнению двух строк.
Второе: Да, я думаю, вы правы, он должен вернуть i. Я неправильно понял значение "Минимального циклического сдвига"
.