BF算法 又叫朴素算法,时间复杂度为O(mn),相比KMP算法比较简单,举个例子,对于给定的主字符串“ababbcabcdabcde”和子串“abcd”;我们用i和j来分别遍历两个字符串,比较两个i,j 对应字符串位置的元素是否相等,如果相等则i++,j++去比较下一个元素,如果i和j 对应位置的元素不相等,则j需要退回到子字符串的0号下标位置,而i需要退回到之前的位置+1,这个位置下标也就是i-j+1的位置,然后继续比较,相等i++,j++,不等j需要退回到子字符串的0号下标位置,i需要退回到i-j+1的位置,重复只到找到为止,找到返回i-j,找不到返回-1:
KMP算法 KMP算法的时间复杂度为O(m+n),所以它相比于BF算法O(mn)更为高效,原因在于KMP算法相比于BP算法去掉了很多重复遍历的情况,它的实现过程与BF算法不一样的地方在于,KMP算法的主串i并不会回退,并且j也不会回退到0号位置:
例如: 非但你会发现中间那些步骤都是多余的,由于子串的首位’a’与后面的2、3、4、5位上的字符都是一样的,你直接就可以到最后一步,也就是你直接可以拿next[1]的值去代替后面与它相同的字符的next[j]的值,于是未来避免这种问题我们队next数组进行了改良,得到nextval数组:nextval数组值的推导(它是建立在next[]数组的基础上的):
j 0 1 2 3 4 5 6 7 8 子串 a b a b a a a b a next[j] -1 0 0 1 2 3 1 1 2 nextval[j] -1 0 -1 0 -1 3 1 0 -1 1、当j等于0是,nextval[0] = -1; 2、当j = 1时,因为1号下标的字符‘b’的next值为0,而0号下标的字符为‘a’与‘b’不相等,所nextval[1] = next[1] = 0,维持原值; 3、当j = 2时,因为2号下标的字符‘a’的next值为0,而0号下标的字符为‘a’与‘a’相等,所nextval[2] = nextval[0] = -1; 4、当j = 3时,因为3号下标的字符‘b’的next值为1,而1号下标的字符为‘b’与‘b’相等,所nextval3] = nextval[1] = 0; ……