Existe uma maneira de determinar se uma lista de números inteiros pode ser uma função de prefixo?

Question

Digamos que você tenha

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

ou

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

Você poderia usar, por exemplo, o algoritmo KMP para deduzir a validade das listas acima como prefixo funções?Eu sei que há uma maneira de descobrir se existe uma subseqüência de caracteres em uma seqüência de caracteres usando KMP, mas existe uma maneira de fazer da outra maneira ao redor, começando com a aparente função de prefixo e comprovar que ele é, de fato, uma possível função de prefixo, sem conhecer a seqüência de caracteres de substring em si no início?

Answer 1

Denotar por $p$ a entrada de função de prefixo.Consulte os caracteres de uma palavra ter $p$ como prefixo função de seus índices V $=\{0,1,2,...,\operatorname{comprimento}(p)-1\}$.Vamos manter um conjunto de pares $D$ de elementos de $V$ para representar os caracteres que devem ser diferentes.Finalmente, $V$ vai ser particionado em classes de equivalência, de acordo com os caracteres da palavra que deve ser igual.Eu suponho que a resposta a esta pergunta é dada também que é o alfabeto $\Sigma$ de permissão de cartas para usar.Uma possível variante da questão daria também um dicionário $L$ de permissão de palavras.

Algoritmo

• Um não-zero como primeira entrada diz-lhe de imediato que a sequência não é uma função de prefixo.

• Cada valor positivo em $p$ diz-lhe a igualdade entre determinados pares de caracteres do potencial palavra ter que (supostamente) função de prefixo.Acompanhe as classes de equivalência que estas igualdades definir, talvez com um disjunto do conjunto de dados da união da estrutura.

• Se você alguma vez encontrar-se um aumento de mais de $1$ ($p[k+1]>p[k]+1$) você pode retornar imediatamente que ele não é uma função de prefixo.

• Sempre que, a sequência não aumentar a ele também irá dizer-lhe um par de caracteres que deve ser diferente.Coletar esses pares $D$.

• Executar pelos pares $D$ de vértices que devem ser diferentes.Se qualquer pertencem à mesma classe de retorno false.

• Finalmente, considere o gráfico $G$ com vértices dada pelo classes de equivalência obtidos acima e onde as arestas são os elementos de $D$.Se apenas o alfabeto $\Sigma$ é dado, então vamos calcular se os vértices de $G$ pode ser colorido com os elementos de $\Sigma$ de tal forma que adjacente vértices não ganha a mesma cor.Na variante em que o dicionário $L$ é dado, então vamos verificar se uma palavra qualquer em $L$ tem o comprimento de $p$ e seus personagens que estão em posições de estar no mesmo classes de equivalência são iguais, e os caracteres formando um par, $D$ são diferentes.Se estas condições forem satisfeitas nós de saída true.Caso contrário, nós saída false.

Vamos fazer os seus exemplos.

Exemplo 1: Dado $p=(0,0,0,1,2,3,4,5,6,7,8,9,10)$, e , em seguida, $V=\{0,1,2,...,12\}$.Que $p[0]=0$ diz-nos que nós não retorno false logo desde o início.Que $p[1]=0$ diz-nos que os caracteres $0$ e $1$ deve ser diferente.Assim, podemos inserir $\{(0,1)\}$ no $D$.Que $p[2]=0$ nos faz inserir $(0,2)$ no $D$.O resto das entradas de $p$ aumentar $1$.Então, nós nunca mais voltar com um false causado por um aumento maior do que $1$.Além disso, não há novas inserções no $D$, mas temos as classes de equivalência $\{0,3,6,9,12\},\{1,4,7,10\},\{2,5,8,11\}$.Desde que os dois pares de $D$, $(0,1)$ e $(0,2)$ não consistem em elementos pertencentes a mesma classe de equivalência, em seguida, nós saída true.Bem, condicional das variantes do problema em que o alfabeto é pequeno e a variante em que o dicionário de todas as palavras são dadas.

Por exemplo, a palavra $1231231231231$ tem $p$ como função de prefixo.Bem, se o alfabeto tem menos de $2$ as letras, em seguida, poderíamos dar o exemplo $1221221221221$.Se o alfabeto tem apenas $1$ letra, nós precisamos de saída false.

Exemplo 2: Dado $p=(0,1,0,1,0,1,2,3,0,1,0,0,1)$, e , em seguida, $V=\{0,1,2,...,12\}$.Que $p[0]=0$ faz a gente não voltar false desde o início.Que $p[1]=1$ diz o uso que $0$ e $1$ estão na mesma classe de equivalência.Que $p[2]=0$ nos faz inserir $(0,2)$ no $D$.Que $p[3]=1$ diz-nos que $0,1,3$ estão na mesma classe de equivalência.Que $p[4]=0$ nos faz inserir $(0,4)$ no $D$.que $[5]=1$, diz-nos que $\{0,1,3,5\}$ está em uma classe de equivalência.Eu acho que você pode continuar.No final, a única classe de equivalência com mais de $1$ elemento $\{0,1,3,5,6,9,12\}$.O resto dos personagens estão em suas próprias classes de equivalência.No $D$ temos os pares $(0,2),(0,4),(0,7),(0,8),(0,10),(0,11)$.Nenhum desses consistir em caracteres da mesma classe de equivalência.Então, nós retorno true.

Por exemplo, a palavra $0010200130450$ tem $p$ como função de prefixo.

Deixe-me acrescentar um exemplo que retorna false para ter um exemplo desse caso.

Exemplo 3: Dado $p=(0,0,1,2,3,4,2,0)$, e , em seguida, $V=\{0,1,2,...,6\}$.Desde $p[0]=0$ nós não retorno false desde o início.Que $p[1]=0$ nos faz inserir $(0,1)$ no $D$.Que $p[2]=1$ diz-nos que $0,2$ estão na mesma classe de equivalência.Que $p[3]=2$, conte-nos o que $1,3$ estão na mesma classe de equivalência e que $0,2$, o que nós já sabíamos também são equivalentes.Que $p[4]=3$ diz que $0,4$ são equivalentes, $1,3$, o que nós sabíamos, e $2,4$, que até agora sabíamos muito.Que $p[5]=4$ diz que $1,3,5$ são equivalentes.Agora, que $p[6]=2$ diz-nos que $6$ e $1$ são equivalentes.Tudo bem até agora.Mas ele também nos diz que $0$ e $5$ são equivalentes.Agora, o problema com isso é que o que torna $1$ (o que é equivalente a $5$) na mesma classe de equivalência, como $0$, mas $(0,1)$ é um par de $D$.Assim, teremos que devolver false.