这里写目录标题

• 1.BP（暴力匹配）
• • 整个算法的分析过程：
• 2.KMP算法
• • 首先我们来思考一下BP的缺点在什么地方：
  • 那么KMP算法怎么回退呢？
  • next[ ]数组的构建和具体含义
  • KMP算法---完整代码如下：

1.BP（暴力匹配）

 假设我们现在有两个字符串：//文本串String s = "BBC ABCDAB ABCDABCDABDE";//待匹配字符串String p = "ABCDABD";

整个算法的分析过程：

	首先我们需要两个指针用于扫描两个字符串：//扫描字符串sint i = 0 ;//扫描字符串pint j = 0 ;

流程如下：

此时就要进行回退操作：

	i = i - j ;j = 0 ; 

代码如下：

    public static int BP(String s , String p){//i----扫描s字符串的指针，j---扫描P字符串的指针int j = 0 ;for (int i = 0 ; i < s.length() ; i++){if (p.charAt(j) == s.charAt(i)){if (j == p.length()-1){return i - (p.length()-1);}j++;}else {/*回退操作：j回退到第一次匹配成功后的下标i回退到待匹配字符的首字符的下标（0）*/i = i - j ;j = 0 ;}}return -1 ;}

2.KMP算法

首先我们来思考一下BP的缺点在什么地方：

 这里我直接指出来，在回退操作中，BP算法直接屏蔽掉了 在当前匹配失败之前匹配成功的字符。这使得我们又要重复扫描一些不需要再次扫描的字符。

那么KMP算法怎么回退呢？

(以下图片资源非本人制作)
我们令 i 不变
而 j = next[ j ] ;
这样做我们就吧重复的AB当作已经匹配好的前缀，再继续扫描字符s
现在我们还不知道next数组是什么，接下里你就会明白了

接下来我们去研究以下next[ ]数组先，一旦next[ ]我们构建完毕，那么KMP算法写起来就十分简单了。

next[ ]数组的构建和具体含义

next[] 数组的含义 ： 前缀与后缀最长的公共字符串的长度
例如：

实现代码如下：

private static int[] getNext(String p){int[] next = new int[p.length()];/*这里i（慢） j（快）相当于一个快慢指针*/int i = -1, j = 0;next[0] = i ;while (j < (p.length()-1)){if (i == -1 || p.charAt(j) == p.charAt(i)){i++;j++;next[j] = i;}else {i = next[i];}}System.out.println(Arrays.toString(next));return next;}

KMP算法—完整代码如下：

	public static int KMP(String s, String p){int[] next = getNext(p);int i = 0 , j = 0 ;while (i < p.length() && j < s.length()){if (i == -1 || s.charAt(j) == p.charAt(i)){i++;j++;}else {i = next[i];}}if (i == p.length())return j - p.length();return -1 ;}private static int[] getNext(String p){int[] next = new int[p.length()];/*这里i（慢） j（快）相当于一个快慢指针*/int i = -1, j = 0;next[0] = i ;while (j < (p.length()-1)){if (i == -1 || p.charAt(j) == p.charAt(i)){i++;j++;next[j] = i;}else {i = next[i];}}System.out.println(Arrays.toString(next));return next;}

KMP算法中i j 的变化如下，会更好的帮助你去理解整个过程。
妙不可言妙不可言

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！