シーケンスは二つの文字列

Question

私は、このタスクを持っての繰り返しのインターリーブであるかどうかを確認します。

X（英語のアルファベットと思う）ある有限固定アルファベットを超える文字列とします。 整数kを指定すると、xのk個のコピーを連結した文字列を表すのにx^k を使用します。 x がHELLOの場合、x^3 はHELLOHELLOHELLOです。 xの繰り返しは、 であり、いくつかの整数kについてx^k という接頭辞があります。したがって、HELLとHELLOHELLはともに HELLOの繰り返しです。 2つの文字列xとyのインターリーブは、xの繰り返し をyの繰り返しでシャッフルすることによって得られる任意の文字列です。例えば、HELwoLOHELLrldwOHは、 HELLOとworldのインターリーブです。 3つの文字列x、y、zを入力とし、zが のxとyのインターリーブであるかどうかを決定するアルゴリズムを記述します。

私は（私たちは、z単語へのポインタ、およびバイナリ木の種類をのみ、指数複雑性を有する溶液で来ていました。すべてのノードでは、私は可能な単語のxとyの現在の状態を（持っています私はzを処理しています。ノードは、zの次の文字がx単語、y単語、またはno単語に追加できるかどうかによって、1/2/no childrenがあります）。指数関数的な複雑さ？

Answer 1

2つの単語xとyの長さがN1とN2であるとします。

（N2 N1）状態と非決定性有限状態機械を構築する。ここで、0 < = N1 < N1及び0 < = N2 < N2。すべての州が受け入れています。

遷移は、次のとおり

c: (n1, n2) --> ((n1 + 1) % N1, n2) if x[n1] == c 
c: (n1, n2) --> (n1, (n1 + 1) % n2) if y[n2] == c 

このNDFSMは、xとyの繰り返しをインターリーブから形成されている文字列を認識する。 https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton#Implementation

ここでは簡単なPython実装です：

はここNDFSMを実装するためのいくつかの方法です。最悪の場合には

def is_interleaved(x, y, z): 
    states = set([(0, 0)]) 
    for c in z: 
     ns = set() 
     for i1, i2 in states: 
      if c == x[i1]: 
       ns.add(((i1+1)%len(x), i2)) 
      if c == y[i2]: 
       ns.add((i1, (i2+1)%len(y))) 
     states = ns 
    return bool(states) 

print is_interleaved('HELLO', 'world', 'HELwoLOHELLrldwOH') 
print is_interleaved('HELLO', 'world', 'HELwoLOHELLrldwOHr') 
print is_interleaved('aaab', 'aac', 'aaaabaacaab') 

、それはO（N1 * N2 * LEN（Z））の時間で実行されますと、O（N1 * N2）のスペースを使用しますが、多くの場合のために、時間の複雑さ、より良いでしょう文字列xとyが繰り返しない限り、これよりも大きい。