string - Knuth-Morris-Pratt (KMP) 和使用 Ukkonen 算法的后缀树之间的时间复杂度差异。

Question

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

Answer 1

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