string - Knuth–Morris–Pratt (KMP) 与使用 Ukkonen 时间复杂度算法的后缀树之间的区别。

Question

是否可以使用 Ukkonen 算法通过 KMP 和后缀树找到最长公共(public)子串、最长回文子串、最长重复子串、搜索所有模式和子串检查？如果是，那么我应该使用哪一个，因为这两种算法都具有线性时间复杂度？

Answer 1

为了找到最长的公共(public)子串，我会使用具有线性复杂度的 Kadane 算法。对于最长的回文子串，可以选择同样具有线性复杂度的 Manacher 算法。对于重复字符串和搜索所有模式，是的，选择将归结为 KMP 和 Boyer-Moore。至于哪一个，Boyer-Moore 匹配模式的最后一个字符而不是第一个字符，假设如果末尾没有匹配，则无需尝试在开头匹配。 KMP 通过观察出现不匹配的情况来搜索主文本字符串 S 中单词 W 的出现，从而绕过对先前匹配字符的重新检查。这使得 KMP 对于像 ACTGT 这样的小集进行了稍微更好的优化。