检查字符串是否由子字符串列表构建的算法

Question

检查字符串是否由子字符串列表构建的算法

algorithmstringsubstring

16

你有一个字符串和一个字符串数组。如何快速检查此字符串是否可以通过连接数组中的某些字符串来构建？

这是一个理论问题，我不需要它用于实际目的。但我想知道是否有一些好的算法可以解决这个问题。

编辑：阅读了一些答案后，我注意到这可能是一个 NP-完全问题。即使找到一个子集字符串，它们的长度总和与给定字符串相同，也是一个经典的子集求和问题。

因此，我想这并没有容易的答案。

编辑：

现在看起来，这实际上不是 NP 完全问题。太酷了 :-)

编辑：

我已经想出了一个通过了一些测试的解决方案：

def can_build_from_substrings(string, substrings):
    prefixes = [True] + [False] * (len(string) - 1)
    while True:
        old = list(prefixes)
        for s in substrings:
            for index, is_set in enumerate(prefixes):
                if is_set and string[index:].startswith(s):
                    if string[index:] == s:
                        return True
                    prefixes[index + len(s)] = True
        if old == prefixes: # nothing has changed in this iteration
            return False

我认为时间复杂度是O(n * m^3)，其中n是子字符串的长度，m是字符串的长度。你怎么看？

- gruszczy

1

感觉像是背包问题的一个变种。 - Anders Lindahl

2

你能只使用数组中的一个字符串吗？ - Anders Lindahl

12个回答

2

这里有一个想法，虽然不是很快，但可以做到：

- 迭代所有字符串，检查目标字符串是否以它们中的任何一个开头 - 取出目标字符串开头最长的那个字符串，从列表中删除并从主字符串中删除该部分 - 重复上述步骤

当你只剩下长度为0的目标字符串时停止。

正如我之前所说，这绝对不快，但应该可以给你一个基准（“它不应该比这更糟”）。

编辑：

如评论中所指出的，这种方法行不通。你需要存储部分匹配，并在找不到更好的匹配时回溯到它们。

- 当你发现一个字符串是目标字符串的开头时，将其推入列表中。在构建完列表后，你自然会尝试目标字符串中最长的“开头” - 当你发现尝试的开头与剩下的部分不匹配时，尝试下一个最佳开头

这样，你最终会探索整个解空间。对于每个候选的开头，你都会尝试每个可能的尾部。

- cnicutar

根据主字符串的大小，您可能希望使用从该数组中的字符串构建的状态机来查找子字符串匹配项到数组项。运行时，需要考虑字符串可以从任何位置开始，因此初始状态（未检查任何字符）对于每个位置都是可能的 - 需要通常的多状态同时有效的非确定有限自动机样式引擎，即使状态模型可以是确定性的（如果您不想最小化，则可能是一个简单的树）。基本上是具有有限选择正则表达式的正则表达式搜索。 - user180247

一旦你有一组（可能重叠的）匹配子字符串，这就是贪婪（或动态）的时候了。 - user180247

1

最大子字符串的方法，如果从哪里开始字符串将是不正确的...例如，字符串是“abcdefght”，可用的子字符串是“ab”、“abc”、“abcde”、“cdef”、“ght”...在这种情况下，最大的起始子字符串是“abcde”，但实际上构成字符串的子字符串是“ab”、“cdef”、“ght”....所以在第一次遍历中，您将找到所有的子字符串，然后尝试使用回溯进行变化... - S M Kamran

@S M Kamran，好眼力，你说得没错。一次扫描是不够的。 - cnicutar

如果我理解正确，不需要使用数组中的所有子字符串，而是只需使用每个子字符串一次：“4231242”：“312”，“42” NO - “42”，“42”，“312” YES？如果是这样，那么贪婪搜索如何适应呢？ - Marino Šimić

显示剩余8条评论

1

这是我会做的方法。

确定目标字符串的长度。
确定子字符串数组中每个字符串的长度。
确定哪种组合的子字符串可以生成与目标字符串相同长度的字符串（如果有，否则完成）。
生成在步骤3中确定的子字符串组合的所有排列。检查它们是否与目标字符串匹配。

生成所有排列是一个处理器密集型的任务，因此如果您可以减少输入大小，您将获得相当大的效率提升。

- Localghost

步骤 1 到 3 相当于子集和问题，但这仍然比蛮力算法有很大的改进。 :) - Bill the Lizard

首先检查是否可以形成正确长度的字符串可能会节省很多时间。但是，正如您所说，生成排列很慢（因为您会得到很多排列），并且有基于子字符串匹配的方法可以避免考虑其中大部分。 - user180247

1

受@cnicutars答案的启发：

function Possible(array A, string s)
- 如果s为空，则返回true。
- 计算数组P，其中包含所有是s前缀的A中的字符串。
- 如果P为空，则返回false。
- 对于P中的每个字符串p：
  - 如果Possible(A with p removed, s with prefix p removed)返回true，则返回true
- 返回false

- Anders Lindahl

去掉字符串s中的字符p -> 移除，多个出现不同，如果你在一个地方或另一个地方删除它会有很大变化，可能会出现假阴性："1234123" : "12","34","123" - Marino Šimić

应该从 S 的开头删除 p，因为它是一个前缀。我已经更新了我的答案以澄清。 - Anders Lindahl

0

你需要的是一个解析器。解析器将检查某个单词是否属于某种语言。我不确定你的问题的确切计算复杂度。以上一些似乎是正确的（根本不需要穷举搜索）。有一件事可以确定，它不是NP-Complete。

你的语言字母表将是所有小子字符串。你要找的单词就是你拥有的字符串。正则表达式可以是简单的Kleene星号，或者是仅由Or组成的非常简单的上下文无关文法。

算法中的主要问题是：如果某些子字符串实际上是其他子字符串的子字符串...也就是说，如果我们有子字符串："ab"，"abc"，"abcd"，...，在这种情况下，检查子字符串的顺序将改变复杂性。为此，我们有LR解析器。我想它们是解决这类问题的最佳选择。

我会尽快为您找到确切的解决方案。

- AJed

0

有两个选项浮现在脑海中，但它们都不太优雅。

1）暴力破解：像密码生成器一样进行操作，即word1+word1+word1 > word1+word1+word2 > word1+word1+word3等等

其中的诀窍在于长度，因此您必须尝试所有2个或更多单词的组合，并且您不知道要设置限制的位置。非常耗时。

2）获取问题字符串并对其运行每个单词的查找。也许检查长度，如果大于0，则再次执行。一直重复此过程，直到达到无法找到更多结果为止。如果达到0，则是胜利，否则是失败。我认为这种方法比第一种好得多，但我想有人会有更好的建议。

- lupos

0

在我看来，一个问题可以通过简单的线性遍历数组和比较来解决。然而可能需要多次遍历。您可以设计一种策略来最小化遍历次数。例如，在第一次遍历中构建原始字符串的所有子字符串的子数组。然后线性地尝试不同的变化。

- S M Kamran

将大小为N的每个排列称为N的排列，对于与原始字符串大小相等的子字符串中的每个排列进行检查，如果没有，则对N + 1项进行排列，以此类推。 - Marino Šimić

感谢您为此提供了一个花哨的关键字 :P - S M Kamran

0

这里有一个大致的想法，应该可以解决问题。

将源字符串复制到一个新字符串中
当复制字符串仍然有数据并且仍然有子字符串时 a. 获取一个子字符串，如果copy.contains(substr)，则copy.remove(substr)
如果复制为空，则可以构造字符串
如果复制不为空，则丢弃从字符串中删除的第一个子字符串并重复。
如果所有子字符串都消失了，但复制仍然不为空，则无法构造它。

编辑：可能改进此方法的一种方法是首先迭代所有子字符串并丢弃不包含在主字符串中的任何子字符串。然后执行上述步骤。

- pstrjds

你可以通过长度检查和其他方法来改进它，这只是一个粗略的想法。 - pstrjds

1

子字符串可以出现在多个位置，从一个位置或另一个位置删除并不相同，这与其他想法一样会产生错误的负面影响。 - Marino Šimić

@Marino 好主意，我还没有完全想透。 - pstrjds

0

如果每个子字符串只能使用一次，但不必全部使用...

对于与原始字符串大小相等的大小为N的排列中的每个排列，请检查它，如果没有，请对N + 1个项目进行排列，以此类推，直到用尽所有排列。

当然是NP完全问题，速度非常慢，但我认为没有正常的解决方案存在。

为了解释为什么从原始字符串中删除子字符串的解决方案永远不起作用：

有一个字符串“1234123”和数组“12”，“34”，“123”。如果您从开头删除“123”，则会出现错误的负面影响。另一个类似的例子是从末尾删除：“1234123”：“23，”41“，”123“。

通过贪心回溯：（m字符串长度7，n元素数3） - 取最长的：123 - 从第一次出现中删除它O（3） - 尝试其他两个与剩余部分：无法+ O（（n-1）*（m-3）） - 回溯O（1） - 从第二个删除：O（m-3） - 尝试其他两个O（（n-1）* m-3） = O（30）

1 + 2 + 3 的排列组合 = O(3) + O(4) + O(6) = O(13)。因此，在子集长度较小的情况下，排列组合实际上比回溯更快。如果您要查找许多子字符串（在大多数情况下但不是所有情况），则情况会发生变化。

您可以从数组中仅删除不存在的子字符串，以将排列数从 n^n 降低到每个已删除的不存在子字符串的 n^(n-1)。

- Marino Šimić

0

让我建议使用后缀树（使用Ukkonen的在线算法来构建它），这似乎适用于在两个文本中搜索常见子字符串。您可以在维基百科/特殊来源中找到更多信息。任务是

Find all z occurrences of the patterns P1..Pn of total length m
enter code hereas substrings in O(m + z) time.

所以你看，存在一个非常酷的解决方案。希望这对你有用。这实际上更适合重复扫描，而不是单次扫描。

- zubrabubra

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Paul Rosania · Accepted Answer

注意：我在此假设您可以多次使用每个子字符串。您可以通过更改我们定义子问题的方式来推广解决方案以包括此限制。这将对空间和预期运行时间产生负面影响，但问题仍然是多项式的。

这是一个动态规划问题。（也是一个很棒的问题！）

让我们定义composable(S, W)为真，如果字符串S可以使用子字符串列表W编写。

当且仅当以下条件成立时，S就是可组合的：

S以W中的一个子字符串w开头。
w之后的S的剩余部分也是可组合的。

让我们写一些伪代码：

COMPOSABLE(S, W):
  return TRUE if S = "" # Base case
  return memo[S] if memo[S]

  memo[S] = false

  for w in W:
    length <- LENGTH(w)
    start  <- S[1..length]
    rest   <- S[length+1..-1]
    if start = w AND COMPOSABLE(rest, W) :
      memo[S] = true # Memoize

  return memo[S]

假设子字符串的长度不是线性的，对于这个算法的运行时间为O(m*n)，在这种情况下，运行时间将为O(m*n^2)(其中m是子字符串列表的大小，n是所研究的字符串的长度)，它使用O(n)的空间进行记忆化。

(注意，如所述，伪代码使用O(n^2)的空间，但哈希记忆化键可以缓解这个问题。)

编辑

这里有一个可用的Ruby实现：

def composable(str, words)
  composable_aux(str, words, {})
end

def composable_aux(str, words, memo)
  return true if str == ""                # The base case
  return memo[str] unless memo[str].nil?  # Return the answer if we already know it

  memo[str] = false              # Assume the answer is `false`

  words.each do |word|           # For each word in the list:
    length = word.length
    start  = str[0..length-1]
    rest   = str[length..-1]

    # If the test string starts with this word,
    # and the remaining part of the test string
    # is also composable, the answer is true.
    if start == word and composable_aux(rest, words, memo)
      memo[str] = true           # Mark the answer as true
    end
  end

  memo[str]                      # Return the answer
end