问题
假设现在我们面临这样一个问题：有一个文本串S，和一个模式串P，现在要查找P在S中的位置，怎么查找呢？
暴力匹配算法
首先，先理清楚了暴力匹配算法的流程及内在的逻辑：
如果用暴力匹配的思路，并假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置，则有：
1. 如果当前字符匹配成功（即S[i] == P[j]），则i++，j++，继续匹配下一个字符；
2. 如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0。相当于每次匹配失败时，i 回溯，j 被置为0。
简单描述
暴力搜索算法由文本串中从0到n-m所有位置的比较组成，无论是否从模式串的起始位置开始，每次匹配过后，模式串向右移动一位。
暴力搜索算法没有预处理阶段，文本串和模式串需要常量额外空间，在搜索阶段的文本串的字符可以按照任意顺序进行比较，匹配的时间复杂度为O(mn)，
代码实现
统一接口定义
/**
* 字符串匹配
* @author binbin.hou
* @date 2019/3/11
* @since 0.0.1
*/
public interface IStringMatch {
/**
* 匹配
* @param text 全部的字符串
* @param pattern 目标字符串
* @return 对应的索引 -1 标识不存在
*/
int indexOf(final String text, final String pattern);
}
BF 算法实现
/**
* 暴力匹配算法
*
* @author binbin.hou
* @date 2019/3/11
* @since 0.0.1
*/
public class BFStringMatch implements IStringMatch {
/**
* @param text 全部的字符串
* @param pattern 目标字符串
* @return 0.0.1
* @see String#indexOf(char[], int, int, String, int)
*/
@Override
public int indexOf(String text, String pattern) {
if (null == text
|| pattern == null) {
return -1;
}
int textLen = text.length();
int patternLen = pattern.length();
if (textLen < patternLen) {
return -1;
}
// 核心算法
char[] textChars = text.toCharArray();
char[] patternChars = pattern.toCharArray();
// text[i] 对应的下标信息
for (int i = 0; i <= textLen - patternLen; i++) {
// pattern 的下标
for (int j = 0; j < patternLen; j++) {
if (textChars[i + j] == patternChars[j]) {
// 遍历完了 pattern 模式
if (j == patternLen - 1) {
return i;
}
}
}
}
return -1;
}
}
改进版本算法
这个版本有没有什么缺陷呢？
明知道部分已经不再错误了，下次再次循环其实都是无效的，这就造成了不必需的循环。
KMP
那有没有一种算法，让i 不往回退，只需要移动j 即可呢？
答案是肯定的。这种算法就是KMP算法，它利用之前已经部分匹配这个有效信息，保持i 不回溯，通过修改j 的位置，让模式串尽量地移动到有效的位置。
