交错字符串算法

Question

我正试图用轻微的扭曲来解决经典的交错问题。扭曲的是第三个字符串可以是前两个字符串循环的交错。例如：假设str1 =“ABC”和Str2 =“ADC”。然后第三个字符串可以是“ABC”和“ADC”循环的交错。循环可以是（string）^ k的任何前缀，其中k是一些正整数。所以A的循环将是ABCABCA，因为它是str1^2的前缀。

所以澄清例子是以下几点：
STR1等于 “ABC”
STR2 = “ADC”
STR3 = “ABCADCABADCCA” - 查找，如果STR3的交织str1和str2中的循环。

“答案：对，因为STR3是循环的交织：ABCABCA这是str1中的前缀^ 3和环ADCADC是STR2的前缀”

Answer 1

作为一个起点，我建议以下算法是正确的，没有评论其运行时间的最优化：

1. 构建一个接受第一个字符串循环的DFA（让我们称它为“左”），例如(ABC)*(e|A|AB)其中e是接受空字符串的正则表达式。
2. 类似地构造一个接受第二个字符串循环的DFA（称为“right”）。

3. 现在我们构造一个NFA（称之为N表示“不确定性”）为您的交织语言如下：

   • 国N分别对状态（L，R），其中L为L的状态和r是R的状态
   • 有一个从在N-标记为C当且仅当以下两个条件之一（L，R）至（L“ R”）的边缘成立：
     • 有一个边缘从l到l'在L中标记为c并且r = r'，或者从r到r'la存在边缘在R和l = 1'中定位c。
   • （L，R）是最后的N IFF升是在最终的L和R是最终在R.
   • N的开始状态为（L，R）其中，l是L的开始状态且r是R的起始状态

然后我认为ñ接受您的交织语言：通过该NFA接受路径对应于任一“L”或“R”的分配的选择，每个字符以及标记为“L”的字符通过L的接受路径以及标记为“R”的字符通过R的接受路径。

只是为了好玩，我已经把这个想法的一个非常小的实现放在了Haskell中，没有试图花大量的时间来做优化或类似的事情。 （因此，没有最小化的DFA，或试图memoize的状态转换，或类似的东西）。它的工作好了你的榜样，至少：

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) 

下面是一些例子运行在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)