快捷導(dǎo)航

java暴力匹配及KMP算法解決字符串匹配問題示例詳解

更新時(shí)間：2021年11月24日 14:27:09 作者：威斯布魯克.猩猩

這篇文章主要為大家介紹了java算法中暴力匹配算法及KMP算法解決字符串匹配的問題示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步

要解決的問題？

一、暴力匹配算法

一個(gè)圖例介紹KMP算法

String str1 = "BBC ABCDAB ABCDABCDABDE";
String str2 = "ABCDABD";

? ??1.?S[0]為B，P[0]為A，不匹配，執(zhí)行第②條指令：“如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0”，S[1]跟P[0]匹配，相當(dāng)于模式串要往右移動(dòng)一位（i=1，j=0）

??2. S[1]跟P[0]還是不匹配，繼續(xù)執(zhí)行第②條指令：“如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0”，S[2]跟P[0]匹配（i=2，j=0），從而模式串不斷的向右移動(dòng)一位（不斷的執(zhí)行“令i = i - (j - 1)，j = 0”，i從2變到4，j一直為0）?

?3. 直到S[4]跟P[0]匹配成功（i=4，j=0），此時(shí)按照上面的暴力匹配算法的思路，轉(zhuǎn)而執(zhí)行第①條指令：“如果當(dāng)前字符匹配成功（即S[i] == P[j]），則i++，j++”，可得S[i]為S[5]，P[j]為P[1]，即接下來S[5]跟P[1]匹配（i=5，j=1)

??4. S[5]跟P[1]匹配成功，繼續(xù)執(zhí)行第①條指令：“如果當(dāng)前字符匹配成功（即S[i] == P[j]），則i++，j++”，得到S[6]跟P[2]匹配（i=6，j=2），如此進(jìn)行下去

?5. 直到S[10]為空格字符，P[6]為字符D（i=10，j=6），因?yàn)椴黄ヅ?，重新?zhí)行第②條指令：“如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0”，相當(dāng)于S[5]跟P[0]匹配（i=5，j=0）?

??6. 至此，我們可以看到，如果按照暴力匹配算法的思路，盡管之前文本串和模式串已經(jīng)分別匹配到了S[9]、P[5]，但因?yàn)镾[10]跟P[6]不匹配，所以文本串回溯到S[5]，模式串回溯到P[0]，從而讓S[5]跟P[0]匹配。?

而S[5]肯定跟P[0]失配。為什么呢？因?yàn)樵谥暗?步匹配中，我們已經(jīng)得知S[5] = P[1] = B，而P[0] = A，即P[1] != P[0]，故S[5]必定不等于P[0]，所以回溯過去必然會(huì)導(dǎo)致失配。那有沒有一種算法，讓i 不往回退，只需要移動(dòng)j 即可呢？

答案是肯定的。這種算法就是KMP算法，它利用之前已經(jīng)部分匹配這個(gè)有效信息，保持i 不回溯，通過修改j 的位置，讓模式串盡量地移動(dòng)到有效的位置。

public class ViolenceMatch {
	public static void main(String[] args) {
		String str1 = "硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好";
		String str2 = "尚硅谷你尚硅你";
		int index = violenceMatch(str1, str2);
		System.out.println("index=" + index);
	}
	/**
	 * 暴力匹配算法
	 */
	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;// i索引指向s1
		int j = 0;// j索引指向s2
		while (i < s1Len && j < s2Len) {// 保證匹配時(shí)，不越界
			if (s1[i] == s2[j]) {// 匹配ok
				i++;
				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;
		}
	}
}

暴力匹配算法的缺點(diǎn)：大量數(shù)據(jù)使用暴力匹配效率很低

二、KMP算法

關(guān)于KMP算法的學(xué)習(xí)，參考了這篇文章，此博主寫的特別詳細(xì)，大佬！

參考鏈接：https://www.cnblogs.com/zzuuoo666/p/9028287.html

算法介紹

KMP的主要思想是：1. 先得到子串的部分匹配表 2.使用部分匹配表完成KMP匹配?

一個(gè)圖例介紹KMP算法?

?代碼實(shí)現(xiàn)

public class KMPAlgorithm {
	public static void main(String[] args) {
		String str1 = "BBC ABCDAB ABCDABCDABDE";
		String str2 = "ABCDABD";
		int[] next = kmpNext("ABCDABD");
		System.out.println("next=" + Arrays.toString(next));
 		int index = kmpSearch(str1, str2, next);
		System.out.println("index=" + index);
	} 
	/**
	 * kmp搜索算法
	 * 
	 * @param str1 原字符串
	 * @param str2 子串
	 * @param next 部分匹配表，是子串對(duì)應(yīng)的部分匹配表
	 * @return 如果是-1就是沒有匹配到，否則返回第一個(gè)匹配的位置
	 */
	public static int kmpSearch(String str1, String str2, int[] next) {
		// 遍歷
		for (int i = 0, j = 0; i < str1.length(); i++) {
 
			// 需要處理 str1.charAt(i) != str2.charAt(j),去調(diào)整j的大小
			// KMP算法核心點(diǎn)
			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;
	} 
	/**
	 * 獲取到一個(gè)字符串(子串)的部分匹配值表
	 */
	public static int[] kmpNext(String dest) {
		// 創(chuàng)建一個(gè)next數(shù)組保存部分匹配值
		int[] next = new int[dest.length()];
		next[0] = 0;// 如果字符串是長(zhǎng)度為1部分匹配值就是0
		for (int i = 1, j = 0; i < dest.length(); i++) {
			// 當(dāng)dest.charAt(i) != dest.charAt(j)，需要從next[j - 1]獲取新的j
			// 直到發(fā)現(xiàn)有dest.charAt(i) == dest.charAt(j)成立才退出
			// 這是kmp算法核心點(diǎn)
			while (j > 0 && dest.charAt(i) != dest.charAt(j)) {
				j = next[j - 1];
			}
			if (dest.charAt(i) == dest.charAt(j)) {
				j++;
			}
			next[i] = j;
		}
		return next;
	}
}

以上就是java暴力匹配及KMP算法解決字符串匹配問題示例詳解的詳細(xì)內(nèi)容，更多關(guān)于暴力匹配及KMP算法解決字符串匹配的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: