Existe-t-il un moyen de déterminer si une liste d’entiers peut être une fonction préfixe ?

Question

Dis que tu avais

(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)

Pourriez-vous utiliser, par exemple, l'algorithme KMP pour déduire la validité des listes ci-dessus en tant que fonctions de préfixe ?Je sais qu'il existe un moyen de savoir si une sous-chaîne existe dans une chaîne à l'aide de KMP, mais existe-t-il un moyen de le faire dans l'autre sens, en commençant par la fonction de préfixe apparente et en vérifiant qu'il s'agit bien d'une fonction de préfixe possible, sans savoir la chaîne/sous-chaîne elle-même au début ?

Answer 1

Noter par $p$ la fonction de préfixe d’entrée.Fait référence aux caractères d'un mot ayant $p$ comme fonction de préfixe par leurs index $V=\{0,1,2,..., om de l'opérateur{longueur}(p)-1\}$.Nous garderons un ensemble de paires $D$ d'éléments de $V$ pour représenter les personnages qui doivent être différents.Enfin, $V$ sera réparti en classes d'équivalence selon les caractères du mot qui doivent être égaux.Je suppose que pour répondre à cette question, il est également indiqué quel est l'alphabet $\Sigma$ de lettres autorisées à utiliser.Une variante possible de la question donnerait également un dictionnaire $L$ de mots autorisés.

Algorithme

• Une première entrée non nulle vous indique immédiatement que la séquence n'est pas une fonction préfixe.

• Chaque valeur positive dans $p$ vous indique l'égalité entre certaines paires de caractères du mot potentiel ayant cette fonction de préfixe (présomptive).Gardez une trace des classes d'équivalence que ces égalités définissent, peut-être avec un structure de données d'union d'ensembles disjoints.

• Si jamais vous constatez une augmentation de plus de $1$ ($p[k+1]>p[k]+1$), vous pouvez renvoyer immédiatement qu'il ne s'agit pas d'une fonction de préfixe.

• Chaque fois que la séquence n'augmente pas, elle vous indiquera également une paire de caractères qui doivent être différents.Récupérez ces paires dans $D$.

• Géré par les binômes $D$ de sommets qui doivent être différents.S'il y en a qui appartiennent à la même classe, retournez false.

• Enfin, considérons le graphique $G$ avec des sommets donnés par les classes d'équivalence obtenues ci-dessus et où les arêtes sont les éléments de $D$.Si seulement l'alphabet $\Sigma$ est donné, alors nous calculons si les sommets de $G$ peut être coloré avec les éléments de $\Sigma$ tel que les sommets adjacents n'ont pas la même couleur.Dans la variante dans laquelle le dictionnaire $L$ est donné, alors nous vérifions si un mot dans $L$ a la longueur de $p$ et ses caractères qui sont dans des positions étant dans les mêmes classes d'équivalence sont égaux, et les caractères formant une paire dans $D$ sont différents.Si ces conditions sont satisfaites, nous produisons true.Sinon, nous produisons false.

Faisons vos exemples.

Exemple 1: Donné $p=(0,0,0,1,2,3,4,5,6,7,8,9,10)$, alors $V=\{0,1,2,...,12\}$.Que $p[0]=0$ nous dit que nous ne reviendrons pas false dès le début.Que $p[1]=0$ nous dit que les personnages $0$ et $1$ doit être différent.On insère donc $\{(0,1)\}$ dans $D$.Que $p[2]=0$ nous fait insérer $(0,2)$ dans $D$.Le reste des entrées de $p$ augmenté de $1$.Donc, nous ne revenons jamais avec un false causée par une augmentation supérieure à $1$.De plus, il n’y a pas de nouvelles insertions dans $D$, mais nous obtenons les classes d'équivalence $\{0,3,6,9,12\},\{1,4,7,10\},\{2,5,8,11\}$.Puisque les deux paires dans $D$, $(0,1)$ et $(0,2)$ ne sont pas constitués d'éléments appartenant à la même classe d'équivalence, nous produisons true.Eh bien, conditionnellement aux variantes du problème dans lesquelles l'alphabet est petit et à la variante dans laquelle le dictionnaire de tous les mots est donné.

Par exemple, le mot $1231231231231$ a $p$ comme fonction de préfixe.Eh bien, si l'alphabet a moins de $2$ lettres alors nous pourrions donner l'exemple $1221221221221$.Si l'alphabet n'a que $1$ lettre, nous aurions besoin de sortir false.

Exemple 2 : Donné $p=(0,1,0,1,0,1,2,3,0,1,0,0,1)$, alors $V=\{0,1,2,...,12\}$.Que $p[0]=0$ nous empêche de revenir false Depuis le début.Que $p[1]=1$ dit d'utiliser ça $0$ et $1$ sont dans la même classe d’équivalence.Que $p[2]=0$ nous fait insérer $(0,2)$ dans $D$.Que $p[3]=1$ nous dit que $0,1,3$ sont dans la même classe d’équivalence.Que $p[4]=0$ nous fait insérer $(0,4)$ dans $D$.que $[5]=1$, nous dit que $\{0,1,3,5\}$ sont dans une classe d’équivalence.Je suppose que vous pouvez continuer.Au final la seule classe d'équivalence avec plus de $1$ l'élément est $\{0,1,3,5,6,9,12\}$.Les autres personnages appartiennent à leurs propres classes d'équivalence.Dans $D$ nous avons les paires $(0,2),(0,4),(0,7),(0,8),(0,10),(0,11)$.Aucun d’entre eux n’est constitué de caractères de la même classe d’équivalence.Alors, nous revenons true.

Par exemple, le mot $0010200130450$ a $p$ comme fonction de préfixe.

Permettez-moi d'ajouter un exemple qui renvoie false pour avoir un exemple de ce cas.

Exemple 3 : Donné $p=(0,0,1,2,3,4,2,0)$, alors $V=\{0,1,2,...,6\}$.Depuis $p[0]=0$ nous ne revenons pas false Depuis le début.Que $p[1]=0$ nous fait insérer $(0,1)$ dans $D$.Que $p[2]=1$ nous dit que $0,2$ sont dans la même classe d’équivalence.Que $p[3]=2$, dis-nous ça $1,3$ sont dans la même classe d'équivalence et que $0,2$, dont nous savions déjà qu'ils étaient également équivalents.Que $p[4]=3$ dit que $0,4$ sont équivalents, $1,3$, ce que nous connaissions, et $2,4$, ce que nous savions maintenant aussi.Que $p[5]=4$ dit que $1,3,5$ sont équivalents.Maintenant que $p[6]=2$ nous dit que $6$ et $1$ sont équivalents.Jusqu'à présent, ça va.Mais cela nous dit aussi que $0$ et $5$ sont équivalents.Maintenant, le problème, c'est que cela fait $1$ (ce qui équivaut à $5$) dans la même classe d'équivalence que $0$, mais $(0,1)$ est une paire dans $D$.Il faudra donc revenir false.