数论对于算法的妙用不仅仅是素性测试
还有一个很经典的问题——字符串匹配
常规的字符串匹配通过逐步移动匹配目标，模式 P的长度和文本规模决定了算法的计算规模。有一种叫做 卡普拉宾的算法，通过将字符转换成数字，然后用一种同余判定运算否定掉大部分不匹配的模式，这种算法和素性测试有异曲同工之妙。
不匹配判定，如果两个数字模一个素数不同余，那么它们肯定不相同，反之则未必，即如果两个数字同余，它们字符未必一样
另一个点，有限字符集总是可以转换成一种对应进制的数字
例如10进制的字符集是 {0, 1, 2, ..., 9} 十六进制是个16个字符集，增加 {a, b, c, d, e, f}
同理汉字，... ， 汉字可以转成一个万进制的数——这有点夸张，但是确实是可以做到的。
这个方法有效的另一个原因和素性测试算法一样——依赖于同余运算的高效
值得注意的是，对字符串生成摘要，过程类似很多的哈希函数，对应的操作很像，实际上拉宾卡普算法的思想有些地方也会描述成哈希函数法。
indexOf 底层就是使用字符串匹配算法 字符串匹配算法很多 BF( Brute Force)算法 暴力匹配算...
KMP字符串匹配算法 先总结一下之前的几种字符串匹配算法 1 BF算法, 最简单的字符串匹配算法, 可以直接使用s...
字符串的查找：朴素查找算法和KMP算法 暴力匹配算法与KMP算法（串的匹配） 字符串查找算法BF和KMP 字符串匹...
字符串模式匹配算法 字符串的KMP算法详解部分匹配表（即）向右移一位就可以得到next数组。字符串模式匹配算法 R...
场景：字符串A为主串，字符串B为模式串，比较字符串B是否能够在字符串A中进行匹配？ 匹配算法：BF算法和RK算法。...
以下为学习 《数据结构与算法之美 -- 字符串匹配》 的记录。 BF算法 即暴力匹配算法，循环遍历匹配。 RK算法...
1.字符串匹配BM算法 在文本中查找字符串匹配算法，坏字符串规则和好后缀规则坏字符串规则： 从后往前匹配，第一个不...
字符串匹配 这章节，我们会讲到几大典型的字符串匹配算法 BF算法 BF算法是最最符合正常人逻辑思维的一种匹配模式，...
本篇介绍一种高效的字符串匹配算法——KMP算法。 KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J....
1、基于字符串匹配的方法 1.1 正向最大匹配分词算法1.2 逆向最大匹配分词算法1.3 双向最大匹配分词算法1....
本文标题：字符串匹配算法随想
本文链接：https://www.haomeiwen.com/subject/nlvnodtx.html
网友评论