确定一个序列是否是两个字符串重复的交错

Question

我有这个任务：

Let x be a string over some finite and fixed alphabet (think English alphabet). Given an integer k we use x^k to denote the string obtained by concatenating k copies of x. If x is the string HELLO then x^3 is the string HELLOHELLOHELLO. A repetition of x is a prefix of x^k for some integer k. Thus HELL and HELLOHELL are both repetitions of HELLO. An interleaving of two strings x and y is any string that is obtained by shuffling a repetition of x with a repetition of y. For example HELwoLOHELLrldwOH is an interleaving of HELLO and world. Describe an algorithm that takes three strings x, y, z as input and decides whether z is an interleaving of x and y.

我只提出了一个解决方案，它具有指数级的复杂性（我们有指向 z 单词的指针，以及一种二叉树。在每个节点中，我都有可能单词 x 的当前状态和 y（一开始都是空白）。我正在处理 z，并且节点有 one/two/no 个子节点，具体取决于 z 的下一个字符是否可以添加到 x 字、y 字或没有字。）我怎么能比指数复杂度更好？

Answer 1

假设 x 和 y 这两个词的长度为 N1 和 N2。

构造一个具有状态 (n1, n2) 的非确定性有限状态机，其中 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 的交错重复形成的字符串。

这里有一些实现 NDFSM 的方法：https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton#Implementation

这是一个简单的 Python 实现。

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) space，但对于许多情况，时间复杂度会比这个好，除非字符串x和y重复。

确定一个序列是否是两个字符串重复的交错

Determine if a sequence is an interleaving of a repetition of two strings

string

algorithm

shuffle

time-complexity

interleave