string - Is it possible to use the KMP algorithm to find a longest substring?

Question

Suppose I have a pattern P and some text T, and I want to find the largest prefix of P that matches a substring of T. Is it possible to modify the KMP algorithm to do such an operation? (If I remember correctly, the KMP algorithm does partial matches, but I am interested in the longest possible match).

Answer 1

当 KMP 正在扫描文本时，KMP 的状态会显示与文本匹配的模式的最长前缀的长度直到当前点，因此您可以记录看到的最大长度以及模式中它所在的点看到了，看起来你可以用它来找到 P 的最长匹配前缀。

另一种方法是将 P 的所有前缀放入 Aho-Corasick。运行时行为将非常相似，尽管它会消耗更多存储。它将允许您使用现有的库 - 如果您有一个用于 Aho-Corasick 的库，而不是修改 KMP 实现。

Answer 2

实际上这是所谓的“扩展-KMP”的典型场景。

请参阅此处和此处的示例代码。