Java实现KMP 算法 _KMP

一、应用场景-字符串匹配问题字符串匹配问题:

有一个字符串 str1= ““硅硅谷尚硅谷你尚硅尚硅谷你尚硅谷你尚硅你好””，和一个子串 str2=“尚硅谷你尚硅你”
现在要判断 str1 是否含有 str2, 如果存在，就返回第一次出现的位置, 如果没有，则返回-1

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

如果当前字符匹配成功(即str1[i]==str2[j])，则i++，j++，继续匹配下一个字符
如果失配(即str1[i]!=str2[j])，令i=i-(j-1)，j=0 。相当于每次匹配失败时，i回溯，j被置为0 。
用暴力方法解决的话就会有大量的回溯，每次只移动一位，若是不匹配，移动到下一位接着判断，浪费了大量
的时间。(不可行!)
暴力匹配算法实现.
代码

package kmp;/** * @program: text * @description: 暴力匹配算法 * @author: min * @create: 2019-10-16 17:26 **/public class ViolenceMatch {public static void main(String[] args) {String str1 = "硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好";String str2 = "尚硅谷你尚硅你~";int index = violenceMatch(str1, str2);System.out.println("index=" + index);}/*** 暴力匹配算法实现** @param str1* @param str2* @return*/private static int violenceMatch(String str1, String str2) {char[] s1 = str1.toCharArray();char[] s2 = str2.toCharArray();int s1Len = s1.length;int s2Len = s2.length;int i = 0; // i索引指向s1int j = 0; // j索引指向s2while (i < s1Len && j < s2Len) {// 保证匹配时，不越界if (s1[i] == s2[j]) {//匹配 oki++;j++;} else { //没有匹配成功//如果失配(即 str1[i]! = str2[j])，令 i = i - (j - 1)，j = 0 。i = i - (j - 1);j = 0;}}//判断是否匹配成功if (j == s2Len) {return i - j;} else {return -1;}}}1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253

三、KMP算法介绍

KMP 是一个解决模式串在文本串是否出现过，如果出现过，最早出现的位置的经典算法
Knuth-Morris-Pratt 字符串查找算法，简称为 “KMP 算法”，常用于在一个文本串 S 内查找一个模式串 P 的出现位置，这个算法由 Donald Knuth、Vaughan Pratt、James H. Morris 三人于 1977 年联合发表，故取这 3 人的姓氏命名此算法.
KMP 方法算法就利用之前判断过信息，通过一个 next 数组，保存模式串中前后最长公共子序列的长度，每次回溯时，通过 next 数组找到，前面匹配过的位置，省去了大量的计算时间

四、KMP 算法最佳应用-字符串匹配问题字符串匹配问题:

有一个字符串str1=“BBCABCDABABCDABCDABDE”，和一个子串str2=“ABCDABD”
现在要判断 str1 是否含有 str2, 如果存在，就返回第一次出现的位置, 如果没有，则返回-1
要求:使用KMP算法完成判断，不能使用简单的暴力匹配算法.

思路分析图解举例来说，有一个字符串 Str1 = “BBC ABCDAB ABCDABCDABDE”，判断，里面是否包含另一个字符串 Str2 = “ABCDABD”?
1.首先，用 Str1 的第一个字符和 Str2 的第一个字符去比较，不符合，关键词向后移动一位

文章插图

2. 重复第一步，还是不符合，再后移

文章插图

3. 一直重复，直到Str1有一个字符与Str2的第一个字符符合为止

文章插图

4. 接着比较字符串和搜索词的下一个字符，还是符合。

文章插图

5.遇到 Str1 有一个字符与 Str2 对应的字符不符合。

文章插图

6.这时候，想到的是继续遍历 Str1 的下一个字符，重复第 1 步。(其实是很不明智的，因为此时 BCD 已经比较过了，没有必要再做重复的工作，一个基本事实是，当空格与 D 不匹配时，你其实知道前面六个字符是”ABCDAB” 。KMP 算法的想法是，设法利用这个已知信息，不要把”搜索位置”移回已经比较过的位置，继续把它向后移，这样就提高了效率。)