<p>假设你的单词有一个合理的大小(比如10个字母)。执行以下操作以实现线性(!)时间复杂性,即<code>O(A+B)</code>:</p>
<ul>
<li>初始化哈希表或trie</li>
<li>对于b中的每个字符串b:
<ul>
<li>对于该字符串的每个子字符串
<ul>
<li>将子字符串添加到hashtable/trie(这不比<code>55*O(B)</code>=<code>O(B)</code>)更糟糕),并使用它所属的字符串的元数据</li>
</ul></li>
</ul></li>
<li>对于a中的每个字符串a:
<ul>
<li>对hashtable/trie执行一个<code>O(1)</code>查询以查找它所在的所有B字符串,生成这些字符串</li>
</ul></li>
</ul>
<p>(在写下这个答案时,如果OP的“单词”是有界的,还没有反应。如果它们是无界的,这个解决方案仍然适用,但是有一个<code>O(maxwordsize^2)</code>的依赖关系,尽管实际上它在实践中更好,因为并非所有单词的大小都相同,所以它可能与分布正确的<code>O(averagewordsize^2)</code>一样好。例如,如果所有单词的大小都是20,那么问题大小将比大小为10的情况下增加4倍。但是,如果从10到20的大小增加足够少的单词,那么复杂性不会有太大变化。)</p>
<p><strong>编辑:</strong><a href="https://stackoverflow.com/q/8289199/711085">https://stackoverflow.com/q/8289199/711085</a>实际上是一个理论上更好的答案。在这个答案发布之前,我正在查看维基百科的链接页面,当时我在想“字符串大小的线性不是你想要的”,后来才意识到这正是你想要的。您构建regexp<code>(Aword1|Aword2|Aword3|...)</code>的直觉是正确的,因为在幕后生成的有限自动机如果支持同时重叠匹配,那么它将快速执行匹配,而不是所有regexp引擎都可能这样做。最终,您应该使用什么取决于您是否计划重用As或Bs,或者这只是一次性的事情。上面的技术更容易实现,但只有在单词有界的情况下才有效(如果不拒绝超过一定大小限制的单词,则会引入DoS漏洞),但如果您不希望使用<a href="http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm" rel="nofollow noreferrer">Aho-Corasick string matching finite automaton</a>或类似内容,或者它不能作为库使用,则可能是您要寻找的。在</p>