2

我有这个任务：

让 x 是一些有限和固定字母表上的字符串（想想英文字母表）。给定一个整数 k，我们使用 x^k 来表示通过连接 k 个 x 副本获得的字符串。如果 x 是字符串 HELLO，则 x^3 是字符串 HELLOHELLOHELLO。x 的重复是某个整数 k 的 x^k 的前缀。因此，HELL 和 HELLOHELL 都是 HELLO 的重复。两个字符串 x 和 y 的交错是通过将 x 的重复与 y 的重复混洗获得的任何字符串。例如 HELwoLOHELLrldwOH 是 HELLO 和 world 的交错。描述一个将三个字符串 x、y、z 作为输入并确定 z 是否是 x 和 y 的交错的算法。

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

4

1 回答 1

2

假设 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) 空间，但在许多情况下，时间复杂度会比这更好，除非字符串 x 和你是重复的。

于 2016-05-16T04:18:20.843 回答