string - 基于字符串的算法编程

Question

给定一组 10 个符号和一组长度最多为 20 个的字符串（最多 100 个），每个字符串由这些符号组成，找到可以由这些符号组成的最大长度字符串，这些符号没有任何给定的字符串为它的子字符串。如果我们可以有无限长的字符串满足该属性，则打印-1。

除了会随时间呈指数增长的蛮力算法外，我无法为此找到任何解决方案。

任何解决此问题的提示将不胜感激。

Answer 1

给定一组需要匹配的字符串，我的直接反应是使用http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm来创建匹配器。这个匹配器是一个有限状态机，它一次接受一个字符，并根据该字符告诉你接下来会进入哪个状态。

因此，我认为您可以将问题简化为接受有向图和起点并找到通过该图的最长路线，该路线不通过与模式匹配对应的节点 - 我认为我们可以简单地从图中删除。这在http://en.wikipedia.org/wiki/Longest_path中有介绍。构建这个图也是线性的，所以整个事情似乎是 O(n)