美文网首页
字符串匹配算法随想

字符串匹配算法随想

作者: 东方胖 | 来源:发表于2024-03-19 13:38 被阅读0次

    数论对于算法的妙用不仅仅是素性测试
    还有一个很经典的问题——字符串匹配

    常规的字符串匹配通过逐步移动匹配目标,模式 P的长度和文本规模决定了算法的计算规模。有一种叫做 卡普拉宾的算法,通过将字符转换成数字,然后用一种同余判定运算否定掉大部分不匹配的模式,这种算法和素性测试有异曲同工之妙。

    不匹配判定,如果两个数字模一个素数不同余,那么它们肯定不相同,反之则未必,即如果两个数字同余,它们字符未必一样

    另一个点,有限字符集总是可以转换成一种对应进制的数字
    例如10进制的字符集是 {0, 1, 2, ..., 9} 十六进制是个16个字符集,增加 {a, b, c, d, e, f}
    同理汉字,... , 汉字可以转成一个万进制的数——这有点夸张,但是确实是可以做到的。

    这个方法有效的另一个原因和素性测试算法一样——依赖于同余运算的高效

    值得注意的是,对字符串生成摘要,过程类似很多的哈希函数,对应的操作很像,实际上拉宾卡普算法的思想有些地方也会描述成哈希函数法。

    相关文章

      网友评论

          本文标题:字符串匹配算法随想

          本文链接:https://www.haomeiwen.com/subject/nlvnodtx.html