假设我们给出了一个字符串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）时间内解决它。
在python中：
>>> 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)):
...
动态编程方法是从左到右工作，构建一个数组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找到你需要的匹配作为动态程序的输入 - 匹配成本在输入字符串的大小，所有候选字符串的总大小以及输入之间的匹配数量上是线性的。字符串和候选字符串。
我会尝试以下方法：
笔记：
您可以使用Trie数据结构。首先，从L中的字符串构造一个trie。
然后，对于输入字符串S，在trie中搜索S.
在搜索期间，对于作为L中的一个单词的结尾的每个被访问节点，在trie（来自根）上调用具有剩余（但是不匹配）的后缀S的新搜索。因此，我们使用递归。如果你在该过程中消耗了S的所有字符，那么你知道，S是来自L的一些字符串的连接。
我会建议这个解决方案：
假设L是一组唯一的字符串。
两个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
您的算法具有复杂度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）。