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