Golang strings中的Index函数(字符串查找)
版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://vearne.cc 1. 前言 在Golang中strings模块Index原型如下 func Index(s, substr string) int Golang中 substr长度大于64/32(视CPU的情况而定)的情况， 查找采用的rabin-karp算法，它是由Richard M. Karp和 Michael O. Rabin在1987年提出的。（1987年就这么牛了，还让人活不活） 该算法的实际应用是检测抄袭 2. 点评 假定s长度为n, substr长度为m 它的时间复杂度为O(n + m)，最坏情况下的时间复杂度为O(n * m)。 KMP算法的时间复杂度也是O(n + m), 可见它的速度并不慢 它的相比于KMP算法的最大优势是，实现简单，易于理解 2.1 以下是暴力算法的伪码 function NaiveSearch(string s[1..n], string pattern[1..m]) for i from 1 to n-m+1 for j from 1 to m if s[i+j-1] ≠ pattern[j] jump to next iteration of outer loop return i return not found 2.2 以下是rabin-karp算法的伪码 function RabinKarp(string s[1..n], string pattern[1..m]) hpattern := hash(pattern[1..m]); for i from 1 to n-m+1 hs := hash(s[i..i+m-1]) if hs = hpattern if s[i..i+m-1] = pattern[1..m] return i return not found 大家可以看出rabin-karp算法其实是暴力算法的改进版， 简单的说: 就是先匹配Pattern的哈希值，如果hash值相同，才实际进行字符串匹配(line 4/5/6) ...