探究字符串匹配算法：暴力法与KMP算法的Java实现

深藏阁楼爱情的钟 2023-10-15 06:58 163阅读 0赞

## 探究字符串匹配算法：暴力法与KMP算法的Java实现 ##

字符串匹配是计算机科学中的基本问题之一，它涉及在一个主串中查找特定的子串。在本文中，我们将深入探讨暴力法和KMP算法这两种常见的字符串匹配算法，并提供详细的Java代码示例。

### 1. 暴力法（Brute Force） ###

**概念**：暴力法是一种简单直观的字符串匹配算法。它在主串中逐个位置尝试匹配子串，如果匹配失败则将主串和子串的索引向后移动一位。

**代码示例**：

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算法是一种高效的字符串匹配算法，它利用已经匹配过的信息来减少比较次数。它构建了一个部分匹配表（也称为最长前缀后缀表），用于在匹配过程中指导主串和子串的移动。

**代码示例**：

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算法这两种常见的字符串匹配算法。通过详细的Java代码示例和解释，我们希望您能更好地理解这些算法的原理和应用。