深入解析RK算法：原理、应用与优化策略

RK算法：

• RK算法比较的是两个字符串的hash值
• 但是hash值相等，不能完全判断两个字符串相等，还需要逐个字符比较

时间复杂度：O(n)

package main
import "fmt"
/**
* @Description: RK算法实现
* @param s1 主串
* @param s2 模式串
* @return int 匹配成功：返回模式串在主串的第一次出现的位置下标，否则返回-1
*/
func strRK(s1 string, s2 string) int {
// 获取串长度并进行初步判断
var l2 = len(s2)
var l1 = len(s1)
if l1 return -1
}
// 字符串哈希
var h2 = 0
var h1 = 0
for i := 0; i h1 += int(s1[i])
h2 += int(s2[i])
}
si := 0
ei := l2
if h1 != h2 {
// hash移动
for ei h1 -= int(s1[si])
h1 += int(s1[ei])
si++
ei++
if h1 == h2 && isEqual(s1, s2, si, ei) {
return si
}
}
}
return -1
}
/**
* @Description: 字符串是否相同
* @param s1 主串
* @param s2 子串
* @param si 主串开始字符（包含）
* @param ei 主串结束字符（不包含）
* @return bool
*/
func isEqual(s1 string, s2 string, si, ei int) bool {
si2 := 0
si1 := si
for si1 if int(s1[si1]) != int(s2[si2]) {
return false
}
si1++
si2++
}
return true
}
func main() {
s1 := "hello"
s2 := "lo"
ret := strRK(s1, s2)
fmt.Println(ret)
}