12-string
字符串专题
字符串hash进阶
在前面第4章讨论过对只有大小写字母的字符串的hash办法,简单说就是把字母看出26进制,然后换算成10进制 p
为一个mod
为H[i...j]
?
思路:我们当然可以对子串同样进行相同的hash操作,但是这样会造成大量的冗余计算。我们可以利用上面计算的结果来简化操作,H[j]
可以由H[i-1]
一路推导下来: H[j]
可能会小于H[i-1]xp
,直接取模可能得到负值,因此为了得到非负结果,结果取模后再度加一次mod
,然后再取模,保证能够得到正值。 H[i]
之后,按照上面的式子方便的获得所有子串的hash值,用于之后的计算。
可以用于计算两个字符串的最大公共子串(注意不是子序列),只需要比较两个子字符串的所有子串hash是否相同,并取最大值即可;
也可以用于计算字符串的最大回文子串,把原来的字符串反转,然后比较最大的hash相同的公共子串。
最后,如果出现了hash冲突,只需要改变下p
和mod
即可。甚至还可以采用双hash,也就是计算两个不同的hash值一起表示字符串的办法。
KMP算法
接下来讨论字符串匹配问题,KMP算法是三个发明作者的首字母。
思想:核心是设计一个next数组,next[i]=k
表示字符串s[0..i]
的最长相等前缀s[0...k]
和后缀s[i-k...i]
。
获取next数组的代码:
1 | void getNext(char s[], int len) { |
KMP算法就是利用前面的next数组来实现,对于字符串text
和模式串pattern
。计算pattern
的next数组,然后模仿next的计算过程不断去匹配text
。实际上,next
数组的求解过程,就是自身对自身的匹配。
1 | // 返回匹配的字符串个数 |
Gitalk 加载中 ...