Vérifiez si une chaîne donnée peut être créée par un ensemble de caractères découpés dans un article de magazine

Question

"Observer que lorsque vous coupez un personnage sorti d'un magazine, le personnage sur le verso de la page est également supprimé. Donner un algorithme pour déterminer si vous pouvez générer une chaîne de caractères en collant des découpes à partir d'un magazine. Supposons que vous êtes donné une fonction qui permettra d'identifier le personnage et sa position sur le verso de la page pour chaque position de caractère."

Comment puis-je le faire?

Je peux faire une première taille de sorte que si un personnage n'a qu'un seul moyen d'en obtenir ramassé, ses prises d'abord avant de tourner la sous-problème pour la dynamique de la technique, mais qu'après cette première élagage?

Qu'est-ce que le temps et l'espace de la complexité?

Answer 1

Comme @LiKao suggéré, cela peut être résolu à l'aide de débit maxi. Pour construire le réseau de nous faire deux "couches" de sommets: l'un avec tous les personnages distincts dans la chaîne d'entrée et un à chaque position sur la page. Faire une bordure avec une capacité de 1 à partir d'un caractère à une position si cette position n'a que le caractère d'un côté. Faire les bords de la capacité 1 à partir de chaque position de l'évier, et de faire des bords de la source à chaque personnage avec une capacité égale à la multiplicité de ce caractère dans la chaîne d'entrée.

Par exemple, disons que nous sommes à la recherche pour le mot "TOTO" sur une page avec quatre positions:

pos    1 2 3 4
front  F C O Z
back   O O K Z

Nous avons ensuite généré le réseau suivant, en ignorant la position 4, car il ne fournit pas les caractères nécessaires.

Maintenant, nous avons seulement besoin de déterminer si il ya un flux à partir de la source de l'évier de la length("FOO") = 3 ou plus.

Answer 2

Vous pouvez utiliser la programmation dynamique directement.

Nous sommes une chaîne s à n lettres. On nous a donné un ensemble de pièces P = {p_1, ..., p_k}. Chaque pièce a une lettre à l'avant p_i.f et un à l'arrière p_i.b.

Note f(j, p) la fonction qui retourne true s'il est possible de créer des sous-chaîne s_1...s_j à l'aide de morceaux de p \subseteq P, et false sinon.

La suite de récurrence est titulaire: f(n, P) = f(n-1, P-p_1) | f(n-1, P-p_2) | ... | f(n-1, P-p_k)

En anglais de la faisabilité de s à l'aide de toutes les pièces en P, dépend de la faisabilité de la sous-chaîne s_1...s_n-1 donné un pion de moins, et nous essayons de retrait total de tous les morceaux (bien sûr, dans la pratique, nous n'avons pas à éliminer tous les morceaux un par un; nous avons seulement besoin de retirer les pièces pour lesquelles p_i.f == s_n || p_i.b == s_n).

La première condition est que f(1, P-p_1) = f(1, P-p2) = ... = true, en supposant que nous l'avons déjà vérifié a-priori (en temps linéaire) qu'il y a assez de lettres dans P pour couvrir toutes les lettres s.