假设我有一个模式 P 和一些文本 T，我想找到 P 的最大前缀匹配 T 的一个子串。是否可以修改 KMP 算法来做这样的操作？ (如果我没记错的话，KMP 算法会进行部分匹配，但我感兴趣的是最长可能的匹配)。
最佳答案
由于KMP正在扫描文本，KMP的状态显示匹配文本到当前点的模式最长前缀的长度，因此您可以记录看到的最大长度和模式中的点在它被看到了，看起来你可以用它来找到 P 的最长匹配前缀。
另一种方法是将 P 的所有前缀放入 Aho-Corasick。运行时行为将非常相似，尽管它会消耗更多的存储空间。它将允许您使用现有的库 - 如果您有一个用于 Aho-Corasick 的库，而不是修改 KMP 实现。
关于string - 是否可以使用 KMP 算法找到最长的子串？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/22903144/