做网站可以参考的网站,深圳网站设计小程序,品牌网站建设渠道,成品网站w灬源码伊园leetcode-28 实现strStr() 更熟悉的字符串匹配算法可能是KMP算法, 但在Golang中,使用的是Rabin–Karp算法 一般中文译作 拉宾-卡普算法,由迈克尔拉宾与理查德卡普于1987年提出 “ 要在一段文本中找出单个模式串的一个匹配#xff0c;此算法具有线性时间的平均复杂度#xff0… leetcode-28 实现strStr() 更熟悉的字符串匹配算法可能是KMP算法, 但在Golang中,使用的是Rabin–Karp算法 一般中文译作 拉宾-卡普算法,由迈克尔·拉宾与理查德·卡普于1987年提出 “ 要在一段文本中找出单个模式串的一个匹配此算法具有线性时间的平均复杂度其运行时间与待匹配文本和模式串的长度成线性关系。虽然平均情况下此算法表现优异但最坏情况下其复杂度为文本长与模式串长的乘积 尽可能多的利用上一步的结果这是优化时间复杂度的一大核心 对于数字类型的字符串可有如下匹配方法 将该方法扩展到非数字类型的字符串 以上这张图片的LaTex $$\begin{gather} 对于长度为n的字符串 x_{0} x_{1} x_{2} ... x_{n-1},\\其对应的“值”val为\\val x_{0} \times r^{n-1} x_{1}\times r^{n-2} ... x_{n-1}\times r^{0} \\其中r为进制数\end{gather}$ ASCII英语字符与二进制位之间的关系 (其他语言) Unicode将世界上所有的符号都纳入其中 每个符号都对应一个独一无二的编码最多可以容纳1114112个字符(2021年9月公布的14.0.0已经收录超过14万个字符) (有个问题是浪费空间。。) 也译作统一码/万国码/国际码 UTF-8: 使用最广的一种 Unicode 的实现方式 (最大特点是 变长的编码方式) 字符编码笔记ASCIIUnicode 和 UTF-8 中日韩汉字Unicode编码表 源码注释 将源码中的16777619进制改为10进制从字符串31415926中搜索4159 4159 package mainimport ( fmt strconv)func main() { var primeRK uint32 10 sep : 4159 hash : uint32(0) for i : 0; i len(sep); i { //fmt.Println(sep[i]) //fmt.Println(string(sep[i])) next, _ : strconv.Atoi(string(sep[i])) //hash hash*primeRK uint32(sep[i]) hash hash*primeRK uint32(next) fmt.Println(hash) } } 输出为 4414154159 完整的以10为primeRK从31415926中搜索4159的代码 package mainimport ( fmt strconv)const PrimeRKNew 10func main() { str : 31415926 substr : 4159 fmt.Println(最终结果为:, IndexRabinKarpNew(str, substr))}func HashStrNew(sep string) (uint32, uint32) { hash : uint32(0) for i : 0; i len(sep); i { //fmt.Println(sep[i]) //fmt.Println(string(sep[i])) next, _ : strconv.Atoi(string(sep[i])) //hash hash*primeRK uint32(sep[i]) hash hash*PrimeRKNew uint32(next) fmt.Println(hash) } var pow, sq uint32 1, PrimeRKNew for i : len(sep); i 0; i 1 { fmt.Println(i is:, i, ---, i1 is:, i1) if i1 ! 0 { pow * sq } sq * sq fmt.Println(pow is:, pow) } return hash, pow}func IndexRabinKarpNew(s, substr string) int { // Rabin-Karp search hashss, pow : HashStrNew(substr) fmt.Println(hashss, pow:, hashss, pow) fmt.Println(~~~分割线~~~) n : len(substr) var h uint32 for i : 0; i n; i { next1, _ : strconv.Atoi(string(s[i])) //h h*PrimeRKNew uint32(s[i]) fmt.Println(next1 is:, next1) h h*PrimeRKNew uint32(next1) } fmt.Println(h即T串初始值为:, h) if h hashss s[:n] substr { return 0 } for i : n; i len(s); { h * PrimeRKNew fmt.Println(h*:, h) last, _ : strconv.Atoi(string(s[i])) //当前T串的最后一个元素 fmt.Println(last is:, last) //h uint32(s[i]) h uint32(last) fmt.Println(h:, h) //h - pow * uint32(s[i-n]) first, _ : strconv.Atoi(string(s[i-n])) //当前T串的第一个元素 fmt.Println(first is:, first) h - pow * uint32(first) fmt.Println(h-:, h) i fmt.Println(---下次循环的 i为 ---, i) if h hashss s[i-n:i] substr { //s[i-n:i]为当前的T串 return i - n } } return -1} 输出为 4414154159i is: 4 --- i1 is: 0pow is: 1i is: 2 --- i1 is: 0pow is: 1i is: 1 --- i1 is: 1pow is: 10000hashss, pow: 4159 10000~~~分割线~~~next1 is: 3next1 is: 1next1 is: 4next1 is: 1h即T串初始值为: 3141h*: 31410last is: 5h: 31415first is: 3h-: 1415---下次循环的 i为 --- 5h*: 14150last is: 9h: 14159first is: 1h-: 4159---下次循环的 i为 --- 6最终结果为: 2 strings.Contains()源码阅读暨internal/bytealg初探 书籍推荐 柔性字符串匹配 牛刀小试: 力扣28. 实现strStr() 力扣187. 重复的DNA序列 力扣686. 重复叠加字符串匹配 另 除去KMP和RK算法字符串匹配还有 Boyer-Moore算法(简称BM算法)系列算法其核心思想是 “ 在字符串匹配过程中模式串发现不匹配时跳过尽可能多的字符以进行下一步的匹配从而提高匹配效率 BM算法的简化版Horspool算法 以及性能更好的Sunday算法 Python用的也不是KMP而是boyer-moore和horspool, 源码点此 KMP 算法的实际应用有哪些 图解字符串匹配之Horspool算法和Boyer-Moore算法 本文由 mdnice 多平台发布
