作者：京东零售 李文涛
一、简介1.1 Background字符串匹配在文本处理的广泛领域中是一个非常重要的主题。字符串匹配包括在文本中找到一个，或者更一般地说，所有字符串(通常来讲称其为模式)的出现。该模式表示为p=p[0..m-1];它的长度等于m。文本表示为t=t[0..n-1],它的长度等于n。两个字符串都建立在一个有限的字符集上。
一个比较常见的字符串匹配方法工作原理如下。在一个大小通常等于m的窗口帮助下扫描文本。首先将窗口和文本的左端对齐，然后将窗口的字符与文本中的字符进行比较，这一特定的工作被称为尝试，在完全匹配或不匹配之后，将窗口移到右侧。继续重复同样的过程，直到窗口的右端超过文本的右端，一般称为滑动窗口机制。
BF算法检查文本中0到n-m之间的所有位置，是否有模式从那里开始出现。然后，在每次尝试之后，它将模式串向右移动一个位置。
BF算法不需要预处理阶段，除了模式和文本之外，还需要一个恒定的额外空间。在搜索阶段，文本字符比较可以以任何顺序进行。该搜索阶段的时间复杂度为O(mn)。
public static int strMatch(String s, String p){
int i = 0, j = 0;
while(i < s.length() && j < p.length()){
if(s.charAt(i) == p.charAt(j)){
i ;
j ;
}else{
i = i - j 1;
j = 0;
}
if (j == p.length()){
return i - j;
}
}
return -1;
}
二、KMP
先回顾下brute force中匹配的情况。我们在文本串BBC#ABCDAB$ABCDABCDABDE中查找模式串ABCDABD，文本串中第1个字符“B”与模式串中第1个字符“A”不匹配，所以我们将模式传后移一位。
