Z Algorithm 一个和KMP,Boyer Moore并列的字符串搜索

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: s+’$’+p =abc$abaedfbabcabd

z: [0, 0, 0, 0, 2, 0, 1, 0, 0, 0, 0, 3, 0, 0, 2, 0, 0]

这里因为我们知道s的长度是3, 所以数组中的3代表这完全匹配.即是答案.

下面是计算zfunction的code, 我发现GeeksforGeek上的code有点麻烦,写了一下自己的: