探究字符串匹配算法：暴力法與KMP算法的Java實(shí)現(xiàn)

字符串匹配是計(jì)算機(jī)科學(xué)中的基本問題之一，它涉及在一個(gè)主串中查找特定的子串。在本文中，我們將深入探討暴力法和KMP算法這兩種常見的字符串匹配算法，并提供詳細(xì)的Java代碼示例。

1. 暴力法（Brute Force）

概念：暴力法是一種簡單直觀的字符串匹配算法。它在主串中逐個(gè)位置嘗試匹配子串，如果匹配失敗則將主串和子串的索引向后移動(dòng)一位。

代碼示例：

public?class?BruteForceMatcher?{public?static?int?bruteForceSearch(String?text,?String?pattern)?{int?n?=?text.length();int?m?=?pattern.length();for?(int?i?=?0;?i?<=?n?-?m;?i++)?{int?j?=?0;while?(j?<?m?&&?text.charAt(i?+?j)?==?pattern.charAt(j))?{j++;}if?(j?==?m)?{return?i;?//?匹配成功，返回索引}}return?-1;?//?未找到匹配}public?static?void?main(String[]?args)?{String?text?=?"ABABABAABCABAB";String?pattern?=?"ABC";int?index?=?bruteForceSearch(text,?pattern);if?(index?!=?-1)?{System.out.println("在索引?"?+?index?+?"?處找到匹配。");}?else?{System.out.println("未找到匹配。");}}
}

2. KMP算法

概念：KMP算法是一種高效的字符串匹配算法，它利用已經(jīng)匹配過的信息來減少比較次數(shù)。它構(gòu)建了一個(gè)部分匹配表（也稱為最長前綴后綴表），用于在匹配過程中指導(dǎo)主串和子串的移動(dòng)。

代碼示例：

public?class?KMPMatcher?{public?static?int[]?computePrefixTable(String?pattern)?{int?m?=?pattern.length();int[]?prefixTable?=?new?int[m];int?j?=?0;for?(int?i?=?1;?i?<?m;?i++)?{while?(j?>?0?&&?pattern.charAt(i)?!=?pattern.charAt(j))?{j?=?prefixTable[j?-?1];}if?(pattern.charAt(i)?==?pattern.charAt(j))?{j++;}prefixTable[i]?=?j;}return?prefixTable;}public?static?int?kmpSearch(String?text,?String?pattern)?{int?n?=?text.length();int?m?=?pattern.length();int[]?prefixTable?=?computePrefixTable(pattern);int?j?=?0;for?(int?i?=?0;?i?<?n;?i++)?{while?(j?>?0?&&?text.charAt(i)?!=?pattern.charAt(j))?{j?=?prefixTable[j?-?1];}if?(text.charAt(i)?==?pattern.charAt(j))?{j++;}if?(j?==?m)?{return?i?-?m?+?1;?//?匹配成功，返回索引}}return?-1;?//?未找到匹配}public?static?void?main(String[]?args)?{String?text?=?"ABABABAABCABAB";String?pattern?=?"ABC";int?index?=?kmpSearch(text,?pattern);if?(index?!=?-1)?{System.out.println("在索引?"?+?index?+?"?處找到匹配。");}?else?{System.out.println("未找到匹配。");}}
}

本文深入探討了暴力法和KMP算法這兩種常見的字符串匹配算法。通過詳細(xì)的Java代碼示例和解釋，我們希望您能更好地理解這些算法的原理和應(yīng)用。