Есть ли способ определить, может ли список целых чисел быть префиксной функцией?

Question

Скажи, что у тебя было

(0,0,0,1,2,3,4,5,6,7,8,9,10)

или

(0,1,0,1,0,1,2,3,0,1,0,0,1)

Не могли бы вы использовать, например, алгоритм KMP для определения достоверности приведенных выше списков в качестве префиксных функций?Я знаю, что есть способ определить, существует ли подстрока в строке, используя KMP, но есть ли способ сделать это наоборот, начиная с очевидной префиксной функции и удостоверяясь, что это действительно возможная префиксная функция, не зная саму строку / подстроку в начале?

Answer 1

Обозначим через $p$ функция префикса ввода.Относятся к символам слова , имеющим $p$ как префиксная функция по их индексам $V=\{0,1,2,...,\имяоператора{длина}(p)-1\}$.Мы сохраним набор пар $D$ из элементов $V$ для представления символов, которые должны отличаться.Наконец-то, $V$ будут разделены на классы эквивалентности в соответствии с символами слова, которые должны быть равны.Я предполагаю, что для ответа на этот вопрос также задано, что такое алфавит $\Сигма$ из разрешенных к использованию букв.Возможный вариант ответа на этот вопрос дал бы также словарь $L$ из разрешенных слов.

Алгоритм

• Ненулевое значение в качестве первой записи сразу говорит вам, что последовательность не является префиксной функцией.

• Каждое положительное значение в $p$ сообщает вам о равенстве между определенными парами символов потенциального слова, имеющего эту (предполагаемую) функцию префикса.Следите за классами эквивалентности, которые определяют эти равенства, возможно, с помощью структура данных объединения непересекающихся множеств.

• Если вы когда-нибудь обнаружите увеличение более чем $1$ ($p[k+1]>p[k]+1$) вы можете немедленно вернуть, что это не префиксная функция.

• Всякий раз, когда последовательность не увеличивается, она также сообщает вам одну пару символов, которые должны отличаться.Соберите эти пары в $D$.

• Управляется парами $D$ из вершин, которые должны быть разными.Если таковые имеются, принадлежат к тому же классу, верните false.

• Наконец, рассмотрим график $G$ с вершинами, заданными классами эквивалентности, полученными выше, и где ребра являются элементами $D$.Если бы только алфавит $\Сигма$ задано, то мы вычисляем, если вершины $G$ может быть окрашен элементами $\Сигма$ такой , что соседние вершины не имеют одинакового цвета.В том варианте , в котором словарь $L$ задается, затем мы проверяем, есть ли какое-либо слово в $L$ имеет длину $p$ и его символы, которые находятся в позициях, относящихся к одним и тем же классам эквивалентности, равны, а символы, образующие пару в $D$ они разные.Если эти условия выполняются, мы выводим true.В противном случае мы выводим false.

Давайте приведем ваши примеры.

Пример 1: Данный $p=(0,0,0,1,2,3,4,5,6,7,8,9,10)$, тогда $V=\{0,1,2,...,12\}$.Это $p[0]=0$ говорит нам, что мы не вернемся false с самого начала.Это $p[1]=0$ говорит нам , что персонажи $0$ и $1$ должно быть, все по-другому.Итак, мы вставляем $\{(0,1)\}$ в $D$.Это $p[2]=0$ заставляет нас вставлять $(0,2)$ в $D$.Остальные записи из $p$ увеличиться на $1$.Таким образом, мы никогда не возвращаемся с false вызвано увеличением, превышающим $1$.Более того, в нем нет новых вставок $D$, но мы получаем классы эквивалентности $\{0,3,6,9,12\},\{1,4,7,10\},\{2,5,8,11\}$.Поскольку две пары в $D$, $(0,1)$ и $(0,2)$ не состоят из элементов, принадлежащих к одному и тому же классу эквивалентности, тогда мы выводим true.Ну, условный из вариантов задачи, в котором алфавит маленький, и вариант, в котором дан словарь всех слов.

Например, слово $1231231231231$ имеет $p$ как функция префикса.Хорошо, если в алфавите меньше, чем $2$ буквы, то мы могли бы привести пример $1221221221221$.Если в алфавите есть только $1$ письмо, нам нужно было бы вывести false.

Пример 2: Данный $p=(0,1,0,1,0,1,2,3,0,1,0,0,1)$, тогда $V=\{0,1,2,...,12\}$.Это $p[0]=0$ заставляет нас не возвращаться false с самого начала.Это $p[1]=1$ советует использовать это $0$ и $1$ находятся в одном и том же классе эквивалентности.Это $p[2]=0$ заставляет нас вставлять $(0,2)$ в $D$.Это $p[3]=1$ говорит нам , что $0,1,3$ находятся в одном и том же классе эквивалентности.Это $p[4]=0$ заставляет нас вставлять $(0,4)$ в $D$.это $[5]=1$, говорит нам , что $\{0,1,3,5\}$ находятся в классе эквивалентности.Я думаю, ты можешь продолжать.В конце концов, единственный класс эквивалентности с более чем $1$ элемент является $\{0,1,3,5,6,9,12\}$.Остальные символы находятся в своих собственных классах эквивалентности.В $D$ у нас есть пары $(0,2),(0,4),(0,7),(0,8),(0,10),(0,11)$.Ни один из них не состоит из символов из одного и того же класса эквивалентности.Итак, мы возвращаемся true.

Например, слово $0010200130450$ имеет $p$ как функция префикса.

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

Пример 3: Данный $p=(0,0,1,2,3,4,2,0)$, тогда $V=\{0,1,2,...,6\}$.С тех пор как $p[0]=0$ мы не возвращаемся false с самого начала.Это $p[1]=0$ заставляет нас вставлять $(0,1)$ в $D$.Это $p[2]=1$ говорит нам , что $0,2$ находятся в одном и том же классе эквивалентности.Это $p[3]=2$, скажи нам , что $1,3$ находятся в одном и том же классе эквивалентности и что $0,2$, которые, как мы уже знали, также эквивалентны.Это $p[4]=3$ рассказывает , что $0,4$ эквивалентны, $1,3$, который мы знали, и $2,4$, что к этому времени мы тоже знали.Это $p[5]=4$ рассказывает , что $1,3,5$ эквивалентны.Так вот, это $p[6]=2$ говорит нам , что $6$ и $1$ эквивалентны.Пока все в порядке.Но это также говорит нам о том , что $0$ и $5$ эквивалентны.Так вот, проблема с этим заключается в том, что это делает $1$ (что эквивалентно $5$) в том же классе эквивалентности , что и $0$, но $(0,1)$ есть ли пара в $D$.Итак, нам придется вернуться false.