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

本文介绍了确定一个序列是否是两个字符串的重复的交织的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我有这个任务：

让x是一个在有限且固定的字母（例如英语字母）上的字符串。给定一个整数k，我们使用x ^ k 表示通过串联x个k副本获得的字符串。如果x 是字符串HELLO，则x ^ 3 是字符串HELLOHELLOHELLO。 x的重复是，它是某个整数k的x ^ k 的前缀。因此，HELL和HELLOHELL都是 HELLO的重复。 两个字符串x和y的交织是通过重复x的重复与y重复获得的任何字符串。例如HELwoLOHELLrldwOH是 HELLO与世界的交织。 描述一种算法，该算法将三个字符串x，y，z作为输入，并确定z是否是x和y的交织。

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，节点是否有一个/两个/没有子代，具体取决于是否可以将z中的下一个字符添加到x词中，y字还是无字。）我怎么能比指数复杂度更好？

I've only come up with a solution, which has exponential complexity (We have pointer to the z word, and kind of a binary tree. In every node I have current states of possible words x and y (at the start both blank). I'm processing z, and nodes has one/two/no children depending on if the next character from z could be added to x word, y word or no word.) How could I get better than exponential complexity?

推荐答案

假设x和y这两个字具有

Suppose the two words x and y have length N1 and N2.

构造一个状态为（n1，n2）的非确定性有限状态机，其中0< = n1< N1和0≤n2 N2

Construct a non-deterministic finite state machine with states (n1, n2) where 0 <= n1 < N1 and 0 <= n2 < N2. All states are accepting.

过渡是：

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的交织重复形成的字符串。

This NDFSM recognises strings that are formed from interleaving repetitions of x and y.

以下是实现NDFSM的一些方法： en.wikipedia/wiki/Nondeterministic_finite_automaton#Implementation

Here's some ways to implement the NDFSM: en.wikipedia/wiki/Nondeterministic_finite_automaton#Implementation

这很简单

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')

在最坏的情况下，它是ll将以O（N1 * N2 * len（z））的时间运行，并且将使用O（N1 * N2）的空间，但是在许多情况下，除非字符串x和y重复，否则时间复杂度会更好。

In the worst case, it'll run in O(N1 * N2 * len(z)) time and will use O(N1 * N2) space, but for many cases, the time complexity will better than this unless the strings x and y are repetitious.