leetcode 题目：28. 实现 strStr()
1. BF 算法（Brute Force）
暴力枚举每一个
text下标textIndex，从textIndex进行匹配。
双指针
-
textIndex：指向文本串的当前位置 -
patternIndex：指向模式串的当前位置
public int indexOf(String text, String pattern) {
// 当 pattern 是空字符串时我们应当返回 0，这与 Java 的 indexOf() 定义相符。
if (pattern.equals("")) {
return 0;
}
// 因为匹配成功时，匹配的串长度和 pattern 串的长度一样
// 又因为 textIndex 表示匹配串的开始下标
// 因此如下等式：
// textIndex + pattern.length() <= text.length();
// 转换一下公式可以得到：
// textIndex <= text.length() - pattern.length();
int maxTextIndex = text.length() - pattern.length();
for (int i = 0; i <= maxTextIndex; ++ i) {
if (match(text, pattern, i)) {
return i;
}
}
return -1;
}
// 从 textIndex 开始匹配
public boolean match(String text, String pattern, int textIndex) {
for (int i = 0; i < pattern.length(); ++ i) {
boolean match = text.charAt(textIndex + i) == pattern.charAt(i);
if (!match) {
return false;
}
}
// 全部匹配成功
return true;
}
最坏的时间复杂度：
O(n * m)，n 为 text 的长度，m 为 pattern 的长度。
打印匹配过程：
public class BFDemo {
public static void main(String[] args) {
String text = "ABABACAB";
String pattern = "ABACA";
int i = indexOf(text, pattern);
System.out.println("index = " + i);
}
public static int indexOf(String text, String pattern) {
// 当 pattern 是空字符串时我们应当返回 0，这与 Java 的 indexOf() 定义相符。
if (pattern.equals("")) {
return 0;
}
// 因为匹配成功时，匹配的串长度和 pattern 串的长度一样
// 又因为 textIndex 表示匹配串的开始下标
// 因此如下等式：
// textIndex + pattern.length() <= text.length();
// 转换一下公式可以得到：
// textIndex <= text.length() - pattern.length();
int maxTextIndex = text.length() - pattern.length();
for (int i = 0; i <= maxTextIndex; ++ i) {
if (match(text, pattern, i)) {
return i;
}
}
return -1;
}
// 从 textIndex 开始匹配
public static boolean match(String text, String pattern, int textIndex) {
int delimiterLength = 40;
printDelimiter('=', delimiterLength, true);
System.out.println(String.format("第 %d 次匹配", textIndex + 1));
printDelimiter('=', delimiterLength, true);
for (int i = 0; i < pattern.length(); ++ i) {
boolean match = text.charAt(textIndex + i) == pattern.charAt(i);
// 打印匹配过程
System.out.println(getMatchText(text, textIndex + i));
printDelimiter(' ', textIndex, false);
System.out.println(getMatchText(pattern, i));
System.out.println(String.format("textIndex = %d, patternIndex = %d, 当前字符匹配结果：%s", textIndex + i, i, match));
printDelimiter('-', delimiterLength, true);
if (!match) {
System.out.println("模式串匹配失败");
return false;
}
}
// 全部匹配成功
System.out.println("模式串匹配成功");
return true;
}
public static String getMatchText(String text, int index) {
String matchChar = "[" + text.substring(index, index + 1) + "]";
return text.substring(0, index) + matchChar + text.substring(index + 1);
}
public static void printDelimiter(char delimiter, int length, boolean newLine) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < length; ++ i) {
sb.append(delimiter);
}
System.out.print(sb);
if (newLine) {
System.out.println();
}
}
}
控制台输出：
========================================
第 1 次匹配
========================================
[A]BABACAB
[A]BACA
textIndex = 0, patternIndex = 0, 当前字符匹配结果：true
----------------------------------------
A[B]ABACAB
A[B]ACA
textIndex = 1, patternIndex = 1, 当前字符匹配结果：true
----------------------------------------
AB[A]BACAB
AB[A]CA
textIndex = 2, patternIndex = 2, 当前字符匹配结果：true
----------------------------------------
ABA[B]ACAB
ABA[C]A
textIndex = 3, patternIndex = 3, 当前字符匹配结果：false
----------------------------------------
模式串匹配失败
========================================
第 2 次匹配
========================================
A[B]ABACAB
[A]BACA
textIndex = 1, patternIndex = 0, 当前字符匹配结果：false
----------------------------------------
模式串匹配失败
========================================
第 3 次匹配
========================================
AB[A]BACAB
[A]BACA
textIndex = 2, patternIndex = 0, 当前字符匹配结果：true
----------------------------------------
ABA[B]ACAB
A[B]ACA
textIndex = 3, patternIndex = 1, 当前字符匹配结果：true
----------------------------------------
ABAB[A]CAB
AB[A]CA
textIndex = 4, patternIndex = 2, 当前字符匹配结果：true
----------------------------------------
ABABA[C]AB
ABA[C]A
textIndex = 5, patternIndex = 3, 当前字符匹配结果：true
----------------------------------------
ABABAC[A]B
ABAC[A]
textIndex = 6, patternIndex = 4, 当前字符匹配结果：true
----------------------------------------
模式串匹配成功
index = 2
从上面 BF 算法的执行过程，可以清晰的看到，文本串在失配（不匹配）时，
textIndex会进行回退。
2. KMP 算法
问：那么有不需要回退 textIndex 的字符串匹配算法吗？
答：有的。
2.1 术语介绍
public class TermShow {
public static void main(String[] args) {
String text = "ABACA";
printNextArray(text);
}
public static void printNextArray(String text) {
int delimiterLength = 50;
System.out.println("text: " + text);
printDelimiter('=', delimiterLength);
for (int i = 0; i < text.length(); ++i) {
printNext(text, i);
printDelimiter('*', delimiterLength);
}
}
public static void printDelimiter(char delimiter, int length) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < length; ++ i) {
sb.append(delimiter);
}
System.out.println(sb);
}
public static void printNext(String text, int endIndex) {
System.out.println("text[0," + endIndex + "]: " + text.substring(0, endIndex + 1));
List<String> properPrefixs = getAndPrintProperPrefix(text, endIndex);
List<String> properSuffixs = getAndPrintProperSuffix(text, endIndex);
printMatchInfo(properPrefixs, properSuffixs);
}
public static List<String> getAndPrintProperPrefix(String text, int endIndex) {
if (endIndex == 0) {
return Collections.emptyList();
}
List<String> properPrefixs = new ArrayList<>();
System.out.print("真前缀：{");
for (int i = 0; i < endIndex; ++ i) {
if (i != 0) {
System.out.print(",");
}
String properPrefix = text.substring(0, i + 1);
System.out.print(" " + properPrefix);
properPrefixs.add(properPrefix);
}
System.out.println(" }");
return properPrefixs;
}
public static List<String> getAndPrintProperSuffix(String text, int endIndex) {
if (endIndex == 0) {
return Collections.emptyList();
}
List<String> properSuffixs = new ArrayList<>();
System.out.print("真后缀：{");
for (int i = endIndex; i >= 1; -- i) {
if (i != endIndex) {
System.out.print(",");
}
String properSuffix = text.substring(i, endIndex + 1);
System.out.print(" " + properSuffix);
properSuffixs.add(properSuffix);
}
System.out.println(" }");
return properSuffixs;
}
public static void printMatchInfo(List<String> properPrefixs, List<String> properSuffixs) {
System.out.print("真前缀和真后缀匹配：");
// 真前缀和真后缀的个数是一样
int length = properPrefixs.size();
for (int i = 0; i < length; ++ i) {
String properPrefix = properPrefixs.get(i);
String properSuffix = properSuffixs.get(i);
if (properPrefix.equals(properSuffix)) {
String format = String.format("([长度=%d], %s) ", properPrefix.length(), properPrefix);
System.out.print(format);
}
}
System.out.println();
}
}
控制台输出：
text: ABACA
==================================================
text[0,0]: A
真前缀和真后缀匹配：
**************************************************
text[0,1]: AB
真前缀：{ A }
真后缀：{ B }
真前缀和真后缀匹配：
**************************************************
text[0,2]: ABA
真前缀：{ A, AB }
真后缀：{ A, BA }
真前缀和真后缀匹配：([长度=1], A)
**************************************************
text[0,3]: ABAC
真前缀：{ A, AB, ABA }
真后缀：{ C, AC, BAC }
真前缀和真后缀匹配：
**************************************************
text[0,4]: ABACA
真前缀：{ A, AB, ABA, ABAC }
真后缀：{ A, CA, ACA, BACA }
真前缀和真后缀匹配：([长度=1], A)
**************************************************
2.2 next 数组
提问：
文本串在第i位，模式串在第j位。pattern[j] != text[i]（失配）后，模式串应该怎么移动呢？
模式串第 j 位失配，说明第 [0, j-1] 位已经匹配，因此模式串 pattern[0, j-1] 和文本串 text[i - j, i - 1] 是相等的。
找到【模式串 [0, j-1] 的真前缀】和【文本串 text[i - j, i - 1] 的真后缀】匹配的最大长度，即【模式串 [0, j-1] 的真前缀】和 模式串 [0, j-1] 的真后缀】匹配的最大长度。
假设【模式串 [0, j-1] 的真前缀】和 模式串 [0, j-1] 的真后缀】匹配的最大长度为 k。
有：pattern[0, k -1] == text[i - k + 1, i]
因此从模式串的第 k 位开始匹配即可，即模式串的当前指针应该跳转到 k。
我们用 next[j] = k 表示模式串第 j 位失配后，应该跳转的位置为 k。
通过以上分析，可以知道 next[j] 还可以表示为【模式串 [0, j-1] 的真前缀】和 模式串 [0, j-1] 的真后缀】匹配的最大长度为 k，不匹配时 k = 0。
2.2.1 递归计算
public class NextDemo {
public static void main(String[] args) {
String text = "ABABCABABD";
for(int i = 0; i < text.length(); ++ i) {
System.out.print(text.charAt(i) + " ");
}
System.out.println();
Arrays.stream(getNext(text)).forEach(v -> System.out.print(v + " "));
System.out.println();
}
public static int[] getNext(String pattern) {
int[] next = new int[pattern.length()];
// [0, -1] 和 [0, 0] 都没有【真前缀】和【真后缀】
next[0] = 0;
if (pattern.length() > 1) {
next[1] = 0;
}
for (int j = 2; j < pattern.length(); ++ j) {
next[j] = getNextValue(pattern, next, j-1, next[j-1]);
}
return next;
}
/**
* 假设：next[j] = k
* 表示 pattern[0, j-1] 子串的【真前缀】和【真后缀】匹配的最大长度为 k
* 也就是说：
* (1) pattern[0, k-1] == pattern[j-1-(k-1), j-1]
*
* 假设：next[k] = m
* 表示 pattern[0, k - 1] 子串的【真前缀】和【真后缀】匹配的最大长度
* 也就是说：
* (2) pattern[0, m-1] == pattern[k-1-(m-1), k-1]
*
* 把等式 (2) 中的 k-1-(m-1) 代入等式 (1) 中，
* 可得：
* 0 + k-1-(m-1) = j-1-(k-1) + k-1-(m-1)
* = j-1-k+1 + k-1-(m-1)
* = j-1-(m-1)
*
* 可得：
* (3) pattern[0, m-1] == pattern[j-1-(m-1), j-1]
*
* 观察可得：等式 (1) 和等式 (3) 是同一种形式
*/
public static int getNextValue(String pattern, int next[], int j, int k) {
// base case
// [0, -1] 和 [0, 0] 都没有【真前缀】和【真后缀】
if (j < 1) return 0;
// 计算 next[j+1]
// case1
// 当 pattern[k] == pattern[j] 时
// next[j+1] = k + 1
if (pattern.charAt(k) == pattern.charAt(j)) {
return k + 1;
}
// case2
// 当 k == 0 && pattern[k] != pattern[j] 时
// next[j+1] = 0
if (k == 0) {
return 0;
}
// case3
// 当 pattern[k] != pattern[j] 时
// k = next[k]，递归计算
return getNextValue(pattern, next, j, next[k]);
}
}
控制台输出：
A B A B C A B A B D
0 0 0 1 2 0 1 2 3 4
next 数组状态转移图
可以看到，模式串失配状态转移图中，在第
0位存在循环。
2.2.2 循环计算
public static int[] getNext(String pattern) {
int[] next = new int[pattern.length()];
// [0, -1] 和 [0, 0] 都没有【真前缀】和【真后缀】
next[0] = 0;
if (pattern.length() > 1) {
next[1] = 0;
}
int k = 0;
for (int j = 2; j < pattern.length(); ++ j) {
// 循环计算
// 结果(1) 为 k = 0
// 结果(2) 为 pattern[k] == pattern[j - 1] 时的 k
while (k > 0 && pattern.charAt(k) != pattern.charAt(j - 1)) {
k = next[k];
}
if (pattern.charAt(k) == pattern.charAt(j - 1)) {
k ++;
}
next[j] = k;
}
return next;
}
2.2.3 next[0] = -1
提问：
文本串在第i位，模式串在第j位。 文本串应该怎么移动呢？
文本串的指针只在两种情况才需要移动：
-
(case 1)：当前位置的字符匹配成功，text[i] == pattern[j]。文本串的当前指针指向下一位（即i++），模式串的当前指针指向下一位（即j++）。 -
(case 2)：模式串第0位失配时，文本串的当前指针指向下一位（即i++），模式串的当前指针保持不变。
我们发现，模式串在第
0位失配时，模式串的指针依然指向0，这样会导致没有办法仅通过next[]的值判断当前的状态。
我们可以引入一个开始状态：-1，让模式串在第 0 位失配后，转移到这个开始状态（即 next[0] = -1）。
这时上面的 (case 2) 就变成：
- 模式串第
0位失配时，文本串的当前指针指向下一位（即i++），模式串的当前指针指向下一位（即j++）。 - 这样指针的移动方式就和
(case 1)的保持了统一。
模式串第 0 位失配时，指针指向 -1
可以看到，通过引入一个开始状态
-1，模式串失配状态转移图中的循环已经不存在。
public static int[] getNext(String pattern) {
int[] next = new int[pattern.length()];
next[0] = -1;
int k = -1;
for (int j = 1; j < pattern.length(); ++ j) {
// 循环计算
// 结果(1) 为 k = -1
// 结果(2) 为 pattern[k] == pattern[j - 1] 时的 k
while (k >= 0 && pattern.charAt(k) != pattern.charAt(j - 1)) {
k = next[k];
}
// -1 ++ 后等于 0
// 所以 next[1] 也可以合并到循环中处理
k ++;
next[j] = k;
}
return next;
}
控制台输出：
A B A B C A B A B D
-1 0 0 1 2 0 1 2 3 4
2.3 kmp 匹配算法
public int indexOf(String text, String pattern) {
// 当 pattern 是空字符串时我们应当返回 0，这与 Java 的 indexOf() 定义相符。
if (pattern.equals("")) {
return 0;
}
int[] next = getNext(pattern);
int textIndex = 0;
int patternIndex = 0;
while (textIndex < text.length() && patternIndex < pattern.length()) {
if (patternIndex == -1
|| text.charAt(textIndex) == pattern.charAt(patternIndex)) {
textIndex++;
patternIndex++;
} else {
patternIndex = next[patternIndex];
}
}
if (patternIndex == pattern.length()) {
return textIndex - patternIndex;
}
return -1;
}
public int[] getNext(String pattern) {
int[] next = new int[pattern.length()];
next[0] = -1;
int k = -1;
for (int j = 1; j < pattern.length(); ++ j) {
// 循环计算
// 结果(1) 为 k = -1
// 结果(2) 为 pattern[k] == pattern[j - 1] 时的 k
while (k >= 0 && pattern.charAt(k) != pattern.charAt(j - 1)) {
k = next[k];
}
// -1 ++ 后等于 0
// 所以 next[1] 也可以合并到循环中处理
k ++;
next[j] = k;
}
return next;
}
时间复杂度：
O(m + n)，n 为 text 的长度，m 为 pattern 的长度。
2.4 打印 KMP 匹配过程
public class KMPDemo {
public static void main(String[] args) {
String text = "ABABACAB";
String pattern = "ABACA";
int i = indexOf(text, pattern);
System.out.println("index = " + i);
}
public static int indexOf(String text, String pattern) {
// 当 pattern 是空字符串时我们应当返回 0，这与 Java 的 indexOf() 定义相符。
if (pattern.equals("")) {
return 0;
}
int[] next = getNext(pattern);
int textIndex = 0;
int patternIndex = 0;
// 匹配次数
int count = 1;
while (textIndex < text.length() && patternIndex < pattern.length()) {
// 打印匹配过程
printDelimiter('*', 40, true);
if (patternIndex == -1) {
System.out.println(String.format("第 %d 次匹配 【patternIndex = -1】【进行下一轮匹配】", count++));
} else {
System.out.println(String.format("第 %d 次匹配", count++));
System.out.println(getMatchText(text, textIndex));
printDelimiter(' ', textIndex - patternIndex, false);
System.out.println(getMatchText(pattern, patternIndex));
boolean match = text.charAt(textIndex) == pattern.charAt(patternIndex);
System.out.println(String.format("textIndex = %d, patternIndex = %d, 当前字符匹配结果：%s", textIndex, patternIndex, match));
}
if (patternIndex == -1
|| text.charAt(textIndex) == pattern.charAt(patternIndex)) {
textIndex++;
patternIndex++;
} else {
patternIndex = next[patternIndex];
}
}
if (patternIndex == pattern.length()) {
return textIndex - patternIndex;
}
return -1;
}
public static int[] getNext(String pattern) {
int[] next = new int[pattern.length()];
next[0] = -1;
int k = -1;
for (int j = 1; j < pattern.length(); ++ j) {
// 循环计算
// 结果(1) 为 k = -1
// 结果(2) 为 pattern[k] == pattern[j - 1] 时的 k
while (k >= 0 && pattern.charAt(k) != pattern.charAt(j - 1)) {
k = next[k];
}
// -1 ++ 后等于 0
// 所以 next[1] 也可以合并到循环中处理
k ++;
next[j] = k;
}
return next;
}
public static String getMatchText(String text, int index) {
String matchChar = "[" + text.substring(index, index + 1) + "]";
return text.substring(0, index) + matchChar + text.substring(index + 1);
}
public static void printDelimiter(char delimiter, int length, boolean newLine) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < length; ++ i) {
sb.append(delimiter);
}
System.out.print(sb);
if (newLine) {
System.out.println();
}
}
}
控制台输出：
****************************************
第 1 次匹配
[A]BABACAB
[A]BACA
textIndex = 0, patternIndex = 0, 当前字符匹配结果：true
****************************************
第 2 次匹配
A[B]ABACAB
A[B]ACA
textIndex = 1, patternIndex = 1, 当前字符匹配结果：true
****************************************
第 3 次匹配
AB[A]BACAB
AB[A]CA
textIndex = 2, patternIndex = 2, 当前字符匹配结果：true
****************************************
第 4 次匹配
ABA[B]ACAB
ABA[C]A
textIndex = 3, patternIndex = 3, 当前字符匹配结果：false
****************************************
第 5 次匹配
ABA[B]ACAB
A[B]ACA
textIndex = 3, patternIndex = 1, 当前字符匹配结果：true
****************************************
第 6 次匹配
ABAB[A]CAB
AB[A]CA
textIndex = 4, patternIndex = 2, 当前字符匹配结果：true
****************************************
第 7 次匹配
ABABA[C]AB
ABA[C]A
textIndex = 5, patternIndex = 3, 当前字符匹配结果：true
****************************************
第 8 次匹配
ABABAC[A]B
ABAC[A]
textIndex = 6, patternIndex = 4, 当前字符匹配结果：true
index = 2
