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

在对于字符串匹配的过程中，通常使用的是暴力匹配，也就说把字符串一一比较，直到匹配成功就进行返回输出。

package StrMatching;public class violencematching {
   	public static int match(String str1, String str2) {
   		char[] s1 = str1.toCharArray();		char[] s2 = str2.toCharArray();		int s1len = s1.length;		int s2len = s2.length;		int i = 0;		int j = 0;		while (i < s1len && j < s2len) {
   // 不越界			if (s1[i] == s2[j]) {
    //匹配成功就进行后移继续匹配				i++;				j++;			} else {
   //匹配不成功就将i移动到j对应的i的位置，j再从0开始				i = i - j + 1;				j = 0;			}		}		if (j == s2len) {
   			return i - j;		} else {
   			return -1;		}	}	public static void main(String[] args) {
   		String str1 = "今天又是美好的一天 美好的太阳";		String str2 = "美好的太阳";		int index = match(str1, str2);		System.out.println("index = " + index);	}}

进行测试，很显然是在第10个位置匹配成功：

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

构建next数组：对一个字符串的元素进行分割，对不同的子串进行匹配。

代码实现：

package StrMatching;import java.util.Arrays;public class KMP {
   	// 获取字符串的部分匹配值	public static int[] MatchValue(String str2) {
   		// 创建数组保存数据		int[] next = new int[str2.length()];		next[0] = 0;// 字符串的长度为1,部分匹配值就是0		for (int i = 1, j = 0; i < next.length; i++) {
   			while (str2.charAt(i) != str2.charAt(j) && j > 0) {
   				j = next[j - 1];			}			if (str2.charAt(i) == str2.charAt(j)) {
    // 部分匹配值加一				j++;			}			next[i] = j;		}		return next;	}	// 查找算法	public static int KMPsearch(String str1, String str2, int[] next) {
   		// 遍历str1		for (int i = 0, j = 0; i < str1.length(); i++) {
   			while (j > 0 && str1.charAt(i) != str2.charAt(j)) {
   				j = next[j - 1];			}			if (str1.charAt(i) == str2.charAt(j)) {
   				j++;			}			if (j == str2.length()) {
   				return i - j + 1;			}		}		return -1;	}	public static void main(String[] args) {
   		String str1 = "ABCDAB ABCDABABCDABDEA";		String str2 = "ABCDABD";		int[] next = MatchValue(str2);		System.out.println("next = " + Arrays.toString(next));		int index = KMPsearch(str1, str2, next);		System.out.println("index = " + index);	}}

在第13个字符的地方匹配成功：

转载地址：http://hgmzi.baihongyu.com/