6

假设给定一个字符串 S，以及一个包含其他一些字符串 L 的列表。

我们如何知道 S 是否是 L 的所有可能连接之一？

例如：

S = "abcdabce"

L = ["abcd", "a", "bc", "e"]

S 是“abcd”+“a”+“bc”+“e”，那么 S 是 L 的串联，而“ababcecd”不是。

为了解决这个问题，我尝试使用 DFS/回溯。伪代码如下：

boolean isConcatenation(S, L) {
    if (L.length == 1 && S == L[0]) return true;
    for (String s: L) {
        if (S.startwith(s)) {
            markAsVisited(s);
            if (isConcatnation(S.exclude(s), L.exclude(s))) 
                return true;
            markAsUnvisited(s);
        }
    }
    return false;
}

然而，DFS/回溯并不是一个有效的解决方案。我很好奇解决这个问题的最快算法是什么，或者是否有任何其他算法可以更快地解决这个问题。我希望有像 KMP 这样的算法，可以在 O(n) 时间内解决它。

4

7 回答 7

3

在蟒蛇中：

>>> yes = 'abcdabce'
>>> no = 'ababcecd'
>>> L = ['abcd','a','bc','e']
>>> yes in [''.join(p) for p in itertools.permutations(L)]
True
>>> no in [''.join(p) for p in itertools.permutations(L)]
False

编辑：正如所指出的，这是n！复杂，所以不适合大L。但是，开发时间不到10秒。

相反，您可以构建自己的置换生成器，从基本置换器开始：

def all_perms(elements):
    if len(elements) <=1:
        yield elements
    else:
        for perm in all_perms(elements[1:]):
            for i in range(len(elements)):
                yield perm[:i] + elements[0:1] + perm[i:]

然后通过跟踪元素的连接是什么来丢弃您不关心的分支，并且只有在它加起来到您的目标字符串时才进行迭代。

    def all_perms(elements, conc=''):
    ...
            for perm in all_perms(elements[1:], conc + elements[0]):
    ...
                if target.startswith(''.join(conc)):
    ...
于 2013-07-18T19:20:17.397 回答
2

动态编程方法是从左到右工作，构建一个数组 A[x]，如果字符串的前 x 个字符形成 L 的可能连接之一，则 A[x] 为真。您可以计算出 A[ n] 通过检查列表中的每个可能的字符串，在前面给出 A[n] - 如果 S 的字符直到第 n 个字符与长度为 k 的候选字符串匹配并且如果 A[nk] 为真，那么您可以设置 A[n ] 真的。

我注意到您可以使用https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm来查找您需要作为动态程序输入的匹配项 - 匹配成本将与输入的大小成线性关系字符串，所有候选字符串的总大小，以及输入字符串和候选字符串之间的匹配数。

于 2013-07-18T19:21:06.430 回答
0

您可以使用Trie数据结构。首先，从 L 中的字符串构造一个 trie。

然后，对于输入字符串 S，在 trie 中搜索 S。

在搜索过程中，对于作为 L 中一个词的结尾的每个访问节点，调用具有 S 的剩余（但不匹配的）后缀的 trie（从根）上的新搜索。因此，我们使用递归。如果您在该过程中使用 S 的所有字符，那么您就会知道，S 是来自 L 的一些字符串的连接。

于 2013-07-18T20:24:47.133 回答
0

i would try the following:

  • find all positions of L_i patterns in S
  • let n=length(S)+1
  • create a graph with n nodes
  • for all L_i positions i: directed edges: node_i --> L_i matches node --> node_{i+length(L_i)}
  • to enable the permutation constrains you have to add some more node/edges to exclude multiple usage of the same pattern
  • now i can ask a new question: is there exists a directed path from 0 to n ?

notes:

  • if there exists a node(0 < i < n) with degree <2 then no match is possible
  • all nodes which have d-=1, d+=1 are part of the permutation
  • bread first or diskstra to look for the solution
于 2013-07-18T20:08:10.497 回答
0

两个 Haskell 命题：

可能有一些反例……只是为了好玩……按自定义排序对 L 进行排序：

import Data.List (sortBy,isInfixOf)

h s l = (concat . sortBy wierd $ l) == s where
  wierd a b | isInfixOf (a ++ b) s = LT
            | isInfixOf (b ++ a) s = GT
            | otherwise            = EQ


更无聊...尝试从 L 构建 S：

import Data.List (delete,isPrefixOf)

f s l = g s l [] where
  g str subs result
    | concat result == s = [result]
    | otherwise   = 
        if null str || null subs' 
           then []
           else do sub <- subs'
                   g (drop (length sub) str) (delete sub subs) (result ++ [sub])
   where subs' = filter (flip isPrefixOf str) subs

输出：

*Main> f "abcdabce" ["abcd", "a", "bc", "e", "abc"]
[["abcd","a","bc","e"],["abcd","abc","e"]]

*Main> h "abcdabce" ["abcd", "a", "bc", "e", "abc"]
False

*Main> h "abcdabce" ["abcd", "a", "bc", "e"]
True
于 2013-07-18T21:03:08.227 回答
0

您的算法具有复杂性 N^2 （N 是列表的长度）。让我们看看实际的 C++

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

typedef pair<string::const_iterator, string::const_iterator> stringp;
typedef vector<string> strings;

bool isConcatenation(stringp S, const strings L) {
    for (strings::const_iterator p = L.begin(); p != L.end(); ++p) {
        auto M = mismatch(p->begin(), p->end(), S.first);
        if (M.first == p->end()) {
            if (L.size() == 1)
                return true;
            strings T;
            T.insert(T.end(), L.begin(), p);
            strings::const_iterator v = p;
            T.insert(T.end(), ++v, L.end());
            if (isConcatenation(make_pair(M.second, S.second), T))
                return true;
        }
    }
    return false;
}

我们可以对其进行排序，而不是循环整个向量，然后在最佳情况下将搜索减少到 O(LOG(N)) 步，其中所有字符串都以不同的字符开头。最坏的情况仍然是 O(N^2)。

于 2013-07-18T21:38:45.803 回答
0

我会建议这个解决方案：

  1. 取一个大小为 256 的数组，它将存储 L 的所有字符串中每个字符的出现计数。现在尝试将其与 S 的每个字符的计数匹配。如果两者不相等，那么我们可以自信地说它们不能形成给定的字符.
  2. 如果计数相同，请执行以下操作，使用 KMP 算法尝试同时查找 S 中 L 中的每个字符串。如果在任何时候有匹配项，我们从 L 中删除该字符串并继续搜索 L 中的其他字符串。如果在任何时候我们找不到匹配项，我们只是打印它无法表示。如果最后 L 为空，我们得出结论 S 确实是 L 的串联。

假设 L 是一组唯一的字符串。

于 2013-07-18T20:28:46.780 回答