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

字符串匹配算法

作者: 曲终人散Li | 来源:发表于2016-10-09 17:07 被阅读37次

    1.朴素算法
    2.RK算法
    3.kmp算法
    详细讲解:
    主要在于搜索字符串相对原字符串需要后移多少位.对比字符串与搜索字符串的第一个字符,若不相同,则讲搜索字符串向后移一位.若相同则对比两者的第二个字符串.当移动到第n个字符时,发现不相同,这是需要就算出部分匹配表,目的在于决定将搜索字符串后移多少位,若还是按老规矩只向后移一位,其实是效率低下的一种做法.因为此时已经知道前n-1个字符是什么了.
    至于如何计算部分匹配表,与字符串前缀 后缀有关系.前缀和后缀字符串最长的共同的字符个数就是该字符的部分匹配值.


    kmp.png

    4.BM算法
    5.Sunday算法

    相关文章

      网友评论

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

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