Massive Algorithms: Approximate string match

近似字符串匹配。比如给定一个长串（10G以上的量级），再给定一个短串（比如长
度为10），然后允许最多有两个字符的匹配误差，让找出长串中所有的匹配位置。

我的想法是滚动hash
比如短串是abcd
那么把它本身和误差为一个或两个char的短串的滚动hash值都算出来放到一个set里面
e.g.
abcd
bbcd
cbcd
…
zbcd

aacd
…
azcd

一共有26*10+45*26*26个备选的短串。
然后在长串里match就行了
hash function随便找个小的质数就ok // 觉得31更好点，比26大，没有collision
比如abcd ==>> a*7^4+b*7^3+c*7^2+d*7

对于长串，每次计算长度为N的值，往右移一个字符，在O(1)也能得到，减去首位，乘以这个质数，加上新的字符

Labels