¿Hay alguna manera de determinar si una lista de números enteros puede ser una función de prefijo?

Question

Di que tuviste

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

o

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

¿Podría utilizar, por ejemplo, el algoritmo KMP para deducir la validez de las listas anteriores como funciones de prefijo?Sé que hay una manera de encontrar si existe una subcadena en una cadena usando KMP, pero ¿hay alguna manera de hacerlo al revés, comenzando en la función de prefijo aparente y averiguando que de hecho es una función de prefijo posible, sin saberlo? ¿La cadena/subcadena misma al principio?

Answer 1

Denotamos por $p$ la función de prefijo de entrada.Hacer referencia a los caracteres de una palabra que tiene $p$ como función de prefijo por sus índices $V=\{0,1,2,..., ombreoperador{longitud}(p)-1\}$.Mantendremos un conjunto de pares. $D$ de elementos de $v$ para representar los personajes que deben ser diferentes.Finalmente, $v$ se dividirá en clases de equivalencia según los caracteres de la palabra que deben ser iguales.Supongo que para responder a esta pregunta también se da cuál es el alfabeto. $\Sigma$ de letras permitidas a utilizar.Una posible variante de la pregunta daría también un diccionario. $l$ de palabras permitidas.

Algoritmo

• Una primera entrada distinta de cero le indica de inmediato que la secuencia no es una función de prefijo.

• Cada valor positivo en $p$ le indica la igualdad entre ciertos pares de caracteres de la palabra potencial que tiene esa función de prefijo (presunta).Lleve un registro de las clases de equivalencia que definen estas igualdades, tal vez con una estructura de datos de unión de conjunto disjunto.

• Si alguna vez encuentra un aumento de más de $1$ ($p[k+1]>p[k]+1$) puede devolver inmediatamente que no es una función de prefijo.

• Siempre que la secuencia no aumente, también te indicará un par de caracteres que deben ser diferentes.Recoge estos pares en $D$.

• Dirigido por las parejas $D$ de vértices que deben ser diferentes.Si alguno pertenece a la misma clase devolver false.

• Finalmente, considere el gráfico. $g$ con vértices dados por las clases de equivalencia obtenidas anteriormente y donde las aristas son los elementos de $D$.Si solo el alfabeto $\Sigma$ está dado, entonces calculamos si los vértices de $g$ Se puede colorear con los elementos de $\Sigma$ tal que los vértices adyacentes no obtienen el mismo color.En la variante en la que el diccionario $l$ se da, luego verificamos si alguna palabra en $l$ tiene la longitud de $p$ y sus personajes que están en posiciones estando en las mismas clases de equivalencia son iguales, y los personajes que forman un par en $D$ son diferentes.Si se cumplen estas condiciones, generamos true.De lo contrario saldremos false.

Hagamos tus ejemplos.

Ejemplo 1: Dado $p=(0,0,0,1,2,3,4,5,6,7,8,9,10)$, entonces $V=\{0,1,2,...,12\}$.Eso $p[0]=0$ nos dice que no volvemos false Desde el principio.Eso $p[1]=0$ nos dice que los personajes $0$ y $1$ debe ser diferente.Entonces, insertamos $\{(0,1)\}$ en $D$.Eso $p[2]=0$ nos hace insertar $(0,2)$ en $D$.El resto de las entradas de $p$ aumentado por $1$.Entonces, nunca regresamos con un false causado por un aumento mayor que $1$.Además, no hay nuevas inserciones en $D$, pero obtenemos las clases de equivalencia $\{0,3,6,9,12\},\{1,4,7,10\},\{2,5,8,11\}$.Dado que los dos pares en $D$, $(0,1)$ y $(0,2)$ no constan de elementos que pertenecen a la misma clase de equivalencia, entonces generamos true.Bueno, condicional de las variantes del problema en la que el alfabeto es pequeño y la variante en la que se da el diccionario de todas las palabras.

Por ejemplo, la palabra $1231231231231$ tiene $p$ como función de prefijo.Bueno, si el alfabeto tiene menos de $2$ letras entonces podríamos dar el ejemplo $1221221221221$.Si el alfabeto sólo tiene $1$ carta, necesitaríamos generar false.

Ejemplo 2: Dado $p=(0,1,0,1,0,1,2,3,0,1,0,0,1)$, entonces $V=\{0,1,2,...,12\}$.Eso $p[0]=0$ hace que no volvamos false desde el principio.Eso $p[1]=1$ dice usar eso $0$ y $1$ están en la misma clase de equivalencia.Eso $p[2]=0$ nos hace insertar $(0,2)$ en $D$.Eso $p[3]=1$ nos dice que $0,1,3$ están en la misma clase de equivalencia.Eso $p[4]=0$ nos hace insertar $(0,4)$ en $D$.eso $[5]=1$, nos dice que $\{0,1,3,5\}$ están en una clase de equivalencia.Supongo que puedes continuar.Al final la única clase de equivalencia con más de $1$ elemento es $\{0,1,3,5,6,9,12\}$.El resto de personajes están en sus propias clases de equivalencia.En $D$ tenemos los pares $(0,2),(0,4),(0,7),(0,8),(0,10),(0,11)$.Ninguno de ellos consta de caracteres de la misma clase de equivalencia.Así que volvemos true.

Por ejemplo, la palabra $0010200130450$ tiene $p$ como función de prefijo.

Permítanme agregar un ejemplo que devuelve false para tener un ejemplo de ese caso.

Ejemplo 3: Dado $p=(0,0,1,2,3,4,2,0)$, entonces $V=\{0,1,2,...,6\}$.Desde $p[0]=0$ no volvemos false desde el principio.Eso $p[1]=0$ nos hace insertar $(0,1)$ en $D$.Eso $p[2]=1$ nos dice que $0,2$ están en la misma clase de equivalencia.Eso $p[3]=2$, dinos que $1,3$ están en la misma clase de equivalencia y que $0,2$, que ya sabíamos que también son equivalentes.Eso $p[4]=3$ dice que $0,4$ son equivalentes, $1,3$, que sabíamos, y $2,4$, que a estas alturas también sabíamos.Eso $p[5]=4$ dice que $1,3,5$ son equivalentes.Ahora eso $p[6]=2$ nos dice que $6$ y $1$ son equivalentes.Está bien hasta ahora.Pero también nos dice que $0$ y $5$ son equivalentes.Ahora, el problema con eso es que eso hace que $1$ (que equivale a $5$) en la misma clase de equivalencia que $0$, pero $(0,1)$ es un par en $D$.Entonces tendremos que regresar. false.