本文共 3856 字，大约阅读时间需要 12 分钟。

题目：

• 如我有两个字符串
  String str1 = "BBC ABCDAB ABCDABCDABDE"
  String str2 = "ABCDABD"
  (空格别忽略了)需要求str2在str1中第一次出现的位置，现在用人眼看来实在下标19处

暴力算法：

过程：

1. 初始化，首先将这两个字符串转成char数组

   并创建连个索引：i、j分别记录str1、str2匹配位置。
   

2. 开始匹配，第一遍

   
   没匹配成功：i往后移一位，j回到str2头

3. 第二遍

   
   省略n遍。。。

4. 第十一遍

   这时候又得回头，索引回溯：
   i = i - j + 1;
   j = 0;

5. 第十二遍

   
   复杂度想想都恐怖
   暴力法实现：

public 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, j = 0;	while (i

KMP算法：

先不讲next数组的形成过程，首先了解以下匹配过程：

next数组

• 我们每次进行移动只关注前面已经匹配的字符，与后面无关，所以next数组的元素就是每个匹配中的字符与前面元素组成的字符串的前缀和后缀的最长的公共元素的长度，因此其求法与动态规划的dp数组相似
• 举例子：
  "ababc"

初步结果：next[] = {0，0，1，2，0}；

说是当上面这么说，那有没有一种好求法呢？

1. 初始值：
   
2. 比较str2.charAt(j) = B,str2.charAt(next[j - 1]) = A，发现不相等并且next[j - 1]==0，不进行递归，置0
   
3. 比较str2.charAt(j) = A,str2.charAt(next[j - 1]) = A，发现相等，置为next[j - 1] + 1=1
   
4. 比较str2.charAt(j) = B,str2.charAt(next[j - 1]) = B，发现相等，置为next[j - 1] + 1=2
   
5. 比较str2.charAt(j) = C,str2.charAt(next[j - 1]) = A，发现不相等，递归到str2.charAt(next[next[j-1]-1])=B不相等，本想再递归，此时发现next[next[j-1]-1]==0不再递归，置为0
   
   如此反复求出next初始数组，再进行右移即可。
   代码实现

public static int[] kmpNext(String dest) {
   	//创建next数组保存部分匹配值	int [] next = new int[dest.length()];	next[0] = 0;	//记录匹配到公共前后缀长度	int len = 0;	int i = 1;	while (i < dest.length()) {
   		if (dest.charAt(i) == dest.charAt(len)) {
   			len++;			next[i] = len;			i++;		}else {
   			if (len > 0) {
   				len = next[len -1];			}else {
   				next[i] = len;				i++;			}		}	}	for (int j = next.length-1; j > 0; j--) {
   		next[j] = next[j - 1]; 	} 	next[0] = -1;	return next;}

完整代码：

package Algorithm;import java.util.Arrays;import javax.xml.soap.Text;public class KMP {
   	public static void main(String[] args) {
   		String s1 = "bbc abcdab abcdabcdabcde";		String s2 = "abcdabcd";		int violenceMatch = Match.violenceMatch(s1, s2);		System.out.println(violenceMatch);		int[] next = Match.kmpNext(s2);		int index = Match.kmpSearch(s1, s2, next);		System.out.println(Arrays.toString(next));		System.out.println(index);			}}class Match {
   	public static int kmpSearch(String str1, String str2, int[] next) {
   		// 遍历		int j = 0;		int i = 0;		while (i < str1.length()) {
   			if (j == str2.length()-1 && str1.charAt(i) == str2.charAt(j) ) {
   				return i - j;				//j = next[j];需要找多个匹配的地方			}			if (str1.charAt(i) == str2.charAt(j)) {
   				i++;				j++;			}else {
   				j = next[j];				if (j == -1) {
   					i++;					j++;				}			}		}		return -1;	}	/**	 * @param dest 要匹配的子字符串	 * @return	 */	public static int[] kmpNext(String dest) {
   		// 创建next数组保存部分匹配值		int[] next = new int[dest.length()];		next[0] = 0;		// 记录匹配到公共前后缀长度		int len = 0;		int i = 1;		while (i < dest.length()) {
   			if (dest.charAt(i) == dest.charAt(len)) {
   				len++;				next[i] = len;				i++;			} else {
   				if (len > 0) {
   					len = next[len - 1];				} else {
   					next[i] = len;					i++;				}			}		}		for (int j = next.length - 1; j > 0; j--) {
   			next[j] = next[j - 1];		}		next[0] = -1;		return next;	}	public 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, j = 0;// i索引指向s1 j指向s2		while (i < s1len && j < s2len) {
   // 匹配不越界			if (s1[i] == s2[j]) {
   				i++;				j++;			} else {
   				i = i - (j - 1);// 指向下一个字符，别多想暴力算法就移动一个位置而已				j = 0;			}		}		if (j == s2len) {
   			return i - j;		} else {
   			return -1;		}	}}

转载地址：https://blog.csdn.net/weixin_43860530/article/details/106863428 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！