KMP算法

1.简介

1.KMP是一个解决模式串在文本串是否出现过,如果出现过,返回最早出现的位置的经典算法;

2.Knuth-Morris-Pratt字符串查找算法,简称为"KMP算法",常用于在一个文本串S内查找一个模式串P的出现位置,这个算法由Donald Knuth、Vaughan Pratt、James H. Morris 三人于1977年联合发表,故取这3人的姓氏命名此算法;

3.KMP方法算法就利用之前判断过的信息,通过一个next数组,保存模式串中前后最长公共子序列的长度,每次回溯时,通过next数组找到前面匹配过的位置,省去了大量的计算时间;

2.应用场景-字符串匹配问题

需求:

①.有一个字符串str1= "BBC ABCDAB ABCDABCDABDE"和一个子串str2=“ABCDABD”;

②.现在要判断str1是否含有str2,如果存在,就返回第一次出现的位置,如果没有,则返回-1;

2.1.暴力匹配算法(不推荐!)

2.1.1.思路分析

如果用暴力匹配的思路,并假设现在str1匹配到i位置,子串str2匹配到j位置,则有:

①.如果当前字符匹配成功(即str1[i] == str2[j]),则i++,j++,继续匹配下一个字符;

②.如果失配(即str1[i]! = str2[j]),令i = i - (j - 1),j = 0.相当于每次匹配失败时,i回溯,j被置为0;

③.用暴力方法解决的话就会有大量的回溯,每次只移动一位,若是不匹配,移动到下