c - 一大串字符串中的最长子串

Question

我有一个巨大的固定文本字符串库，以及一个经常变化的输入字符串。我需要从字符串 s 的开头开始，在最短的时间内找到从库中的任何字符串到 s 的最长匹配子字符串。在一个完美的世界中，我还会从库中返回下一个最长的匹配项，然后返回下一个最佳匹配项，依此类推。这不是最长的公共(public)字符串问题——我不是在寻找库中所有字符串的最长公共(public)字符串……我只需要尽可能快地在 s 和庞大的库中的每个字符串之间找到一个成对的最佳子字符串。

Answer 1

重读后，我认为最好的方法可能是为你的大字符串库构建一个 trie 或前缀树，然后将 s 与之匹配。

这有两个优点。首先，它以(至少在一定程度上)压缩形式存储您的大型图书馆。其次，它或多或少会自动告诉您与给定输入匹配的所有字符串，而不仅仅是最长的字符串。

它也非常适合您的用例——虽然从输入构建 trie 或(尤其是)前缀树需要大量工作，但之后使用它非常快。