1.基本概述
字符串匹配算法用于在一个字符串（称为主串）中查找一个子串（称为模式串）的出现位置或匹配情况。以下是几种常见的字符串匹配算法：
朴素的模式匹配算法（Brute Force）：朴素的模式匹配算法是最简单直接的方法，它从主串的第一个字符开始，依次与模式串的字符进行比较，直到找到完全匹配或者匹配失败为止。时间复杂度为 O(m*n)，其中 m 是主串的长度，n 是模式串的长度。
KMP 算法：KMP 算法是一种高效的字符串匹配算法，它利用了模式串本身的特性，在匹配过程中避免了主串指针的回溯。它的核心是构建一个部分匹配表（也称为失效函数或 Next 数组），用于指导匹配过程中模式串指针的移动。KMP 算法的时间复杂度为 O(m+n)，其中 m 是主串的长度，n 是模式串的长度。
比如这题
2.朴素的模式匹配算法
逻辑：
- 初始化两个指针 i 和 j，分别表示在原始字符串和模式字符串中当前比较的位置。
- 使用两个嵌套的循环，在原始字符串中逐个比较与模式字符串匹配的子串。
- 外层循环控制 i 的移动，内层循环j用于比较原始字符串和模式字符串中的字符是否相等。
- 如果发现字符不相等，则退出内层循环，继续外层循环，移动 i 指针。
- 如果内层循环完成后 j 的值等于模式字符串的长度，表示找到了匹配的子串，返回该子串在原始字符串中的起始位置 i。
代码：
package com.dreams.leetcode;
/**
* 字符串匹配
*/
public class Leetcode28_01 {
static int strStr(String str1, String str2) {
char[] origin = str1.toCharArray(); // 原始
char[] pattern = str2.toCharArray(); // 模式
int i = 0;
int j = 0;
while (i <= origin.length - pattern.length) {
for (j = 0; j < pattern.length; j++) {
if (pattern[j] != origin[i+j]) {
break;
}
}
if (j == pattern.length) {
return i;
}
i++;
}
return -1;
}
public static void main(String[] args) {
System.out.println(strStr("aaacaaab", "aaab"));
}
}
3.KMP 算法
KMP（Knuth-Morris-Pratt）算法是一种字符串匹配算法，用于在一个文本串（text）中查找一个模式串（pattern）的出现位置。它的主要思想是利用已经部分匹配的信息来避免在文本串中不必要的回溯。
最长前后缀数组：只跟模式字符串相关，它的索引就是使用了模式字符串前 j 个字符串 – 1，而值就是最长前后缀的长度（恰好是j要跳转的位置）。
对于位置i，计算其最长前后缀长度lps[i]的方法如下：
- 如果pattern[i] == pattern[j]，则lps[i] = j + 1，表示当前位置的最长前后缀长度为j+1。同时将i++，j++。
- 如果pattern[i] != pattern[j]，且j不是起始位置，则将j更新为lps[j-1]，即回溯到前一个位置的最长前后缀长度，继续比较pattern[i]和pattern[j]。
- 如果回溯后pattern[i] == pattern[j]，则lps[i] = lps[j] + 1；否则lps[i]仍为0。
代码：
package com.dreams.leetcode;
import java.util.Arrays;
/**
* 字符串匹配 - Knuth Morris Pratt 算法
*/
public class Leetcode28_KMP {
static int strStr(String str1, String str2) {
char[] origin = str1.toCharArray(); // 原始
char[] pattern = str2.toCharArray(); // 模式
int[] lps = lps(pattern); // 最长前后缀数组
int i = 0;
int j = 0;
while (pattern.length - j <= origin.length - i) {
// 匹配成功，i++ j++，直到 j==模式字符串长度
if (origin[i] == pattern[j]) {
i++;
j++;
// 匹配失败 j == 0 则 i++
} else if (j == 0) {
i++;
// 匹配失败 j != 0 跳过最长前后缀字符，继续匹配
} else {
j = lps[j - 1];
}
if (j == pattern.length) {
// 找到解
return i - j;
}
}
return -1;
}
/*
最长前后缀数组：只跟模式字符串相关
1. 索引：使用了模式字符串前 j 个字符串 - 1
2. 值：最长前后缀的长度（恰好是j要跳转的位置）
*/
static int[] lps(char[] pattern) {
int[] lps = new int[pattern.length];
int i = 1;
int j = 0;
while (i < pattern.length) {
if (pattern[i] == pattern[j]) {
lps[i] = j + 1;
i++;
j++;
} else if (j == 0) {
i++;
} else {
j = lps[j - 1];
}
}
return lps;
}
public static void main(String[] args) {
System.out.println(Arrays.toString(lps("ababaca".toCharArray())));
}
}
参考
