Interleaving Strings Algorithm

Question

J'essaie de résoudre la question de l'entrelacement classique avec une légère torsion. La torsion est que la troisième chaîne peut être un entrelacement des boucles des deux premières chaînes. Par exemple: Supposons str1 = "ABC" et Str2 = "ADC". Ensuite, la troisième chaîne peut être un entrelacement de boucles de "ABC" et "ADC". Une boucle serait n'importe quel préfixe de (chaîne)^k, où k est un entier positif. Donc une boucle de A serait ABCABCA puisque c'est un préfixe de str1^2.

Ainsi, un exemple de clarifier serait la suivante:
str1 est égal à "ABC"
str2 = "ADC"
Str3 = "ABCADCABADCCA" - Trouvez si str3 est de boucles de entrelacement str1 et str2.

« Réponse: Vrai parce que str3 est l'entrelacement de la boucle. ABCABCA qui est un préfixe de str1^3 et la boucle ADCADC qui est un préfixe de str2 »

Answer 1

En tant que point de départ, je propose à la L'algorithme suivant est correct, sans aucun commentaire sur l'optimisation de son exécution:

1. Construire un DFA (appelons-le L pour "left") qui accepte les boucles de la première chaîne, par ex. (ABC)*(e|A|AB) où e est l'expression régulière qui accepte la chaîne vide.
2. De même, construisez un DFA (appelez-le R pour "right") qui accepte les boucles de la deuxième chaîne.

3. Nous construisons maintenant un NFA (appeler N pour « non déterministes ») pour votre langue désentrelacement comme suit:

   • Etats N sont des paires d'états (l, r) où l est un état de L et r est un état de R.
   • Il y a un bord à partir de (l, r) (l 'r') marqué dans c N ssi une des deux conditions suivantes est vérifiée:
     • Il y a un bord de l à l 'marqué c dans L et r = r', OU
     • Il y a un bord de r à r 'la notée c dans R et l = l '.
   • (l, r) est définitive en N ssi l est finale en L et r est définitive dans R.
   • l'état initial de N est (l, r) où l est l'état de départ de L et r est l'état initial de R.

Je pense que N accepte votre langue désentrelacement: accepter des chemins à travers cette NFA correspondent à un choix d'affectation de « l » ou « R » pour chaque caractère avec un chemin d'acceptation à travers L pour les caractères étiquetés "L" et un chemin d'acceptation à travers R pour les caractères marqués "R". Juste pour le plaisir, j'ai mis en place une très petite implémentation de cette idée dans Haskell, sans essayer de passer beaucoup de temps à faire de l'optimisation ou quoi que ce soit de ce genre. (Donc pas de minimisation de DFA, ou d'essayer de memoize transitions d'état, ou quelque chose comme ça.) Il fonctionne bien pour votre exemple, au moins:

import Data.List 

type Position a = ([a], [a]) 
type DFAState a = (Position a, Position a) 
type NFAState a = [DFAState a] 

initialize :: [a] -> [a] -> NFAState a 
initialize xs ys = [(([], xs), ([], ys))] 

stepPosition :: Eq a => a -> Position a -> [Position a] 
stepPosition x ([], [] ) = [] 
stepPosition x (bs, [] ) = stepPosition x ([], reverse bs) 
stepPosition x (bs, e:es) = [(e:bs, es) | e == x] 

ordNub :: Ord a => [a] -> [a] 
ordNub = concatMap (take 1) . group . sort 

stepDFA :: Ord a => a -> DFAState a -> [DFAState a] 
stepDFA x (l, r) = ordNub 
       $ [(l', r) | l' <- stepPosition x l] 
       ++ [(l, r') | r' <- stepPosition x r] 

stepNFA :: Ord a => a -> NFAState a -> NFAState a 
stepNFA x ss = concatMap (stepDFA x) ss 

evalNFA :: Ord a => [a] -> NFAState a -> Bool 
evalNFA _  [] = False 
evalNFA []  ss = True 
evalNFA (c:cs) ss = evalNFA cs (stepNFA c ss) 

top :: Ord a => [a] -> [a] -> [a] -> Bool 
top ls rs cs = evalNFA cs (initialize ls rs) 

Voici quelques exemples d'exécution dans ghci:

*Main> :set +s 
*Main> top "ABC" "ADC" "ABCADCABADCCA" 
True 
(0.00 secs, 0 bytes) 
*Main> top "ABC" "ADC" "ABCADCABADCCADABCC" 
True 
(0.01 secs, 0 bytes) 
*Main> top "ABC" "ADC" "ABCADCABADCCADADCC" 
False 
(0.00 secs, 0 bytes)