KMP和Boyer Moore应该是最常见的两个子串搜索算法. 相比之下, KMP比较适合用在字符串基数少的string, 比如DNA, 然后BM相反. 和z相比, z的优势也就是短点… 今天看到GeeksforGeeks上介绍了Z function(Z algorithm).我都快忘了还有这个了. Z algorithm的时,空间复杂度和KMP类似, 采用的技术也类似.简单来说, Z algorithm采用了一个Z数组来保留已知子串信息. 和KMP一样, 我们需要预先计算Z数组. 如何计算Z数组?, Z数组的思想就是Longest Common Prefix (最长公共前缀,下面简称lcp). Z数组中在i位的元素表示lcp(s[0,s.length-1], s[i,s.length-1]). 就是包含i位的子串与串s的最长公共前缀. 比如 s: abbabbaa z: [0, 0, 0, 4, 0, 0, 1, 1] 在第二个a的时候, z是4, 表示abba是和s的最长公共子串, 即:lcp(abbabbaa,abbaa) = |abba|= 4. 如何使用z数组呢? 其实很简单, 只要把目标串s和匹配串p放在一个串中, 中间加个特殊符号, 就可以做子串搜索了.比如: s: abc p:abaedfbabcabd our string: […]