算法说明
设主串（下文中我们称作T）为：a b a c a a b a c a b a c a b a a b b
模式串（下文中我们称作W）为：a b a c a b
用暴力算法匹配字符串过程中，我们会把T[0] 跟 W[0] 匹配，如果相同则匹配下一个字符，直到出现不相同的情况，此时我们会丢弃前面的匹配信息，然后把T[1] 跟 W[0]匹配，循环进行，直到主串结束，或者出现匹配成功的情况。这种丢弃前面的匹配信息的方法，极大地降低了匹配效率。
而在KMP算法中，对于每一个模式串我们会事先计算出模式串的内部匹配信息，在匹配失败时最大的移动模式串，以减少匹配次数。
比如，在简单的一次匹配失败后，我们会想将模式串尽量的右移和主串进行匹配。右移的距离在KMP算法中是如此计算的：在已经匹配的模式串子串中，找出最长的相同的前缀和后缀，然后移动使它们重叠。
在第一次匹配过程中
T: a b a c a a b a c a b a c a b a a b b
W: a b a c a b
在T[5]与W[5]出现了不匹配，而T[0]~T[4]是匹配的，其中T[0]~T[4]就是上文中说的已经匹配的模式串子串，移动找出最长的相同的前缀和后缀并使他们重叠：
T: a b a c aa b a c a b a c a b a a b b
W: a b a c a b
然后在从上次匹配失败的地方进行匹配，这样就减少了匹配次数，增加了效率。
然而，如果每次都要计算最长的相同的前缀反而会浪费时间，所以对于模式串来说，我们会提前计算出每个匹配失败的位置应该移动的距离，花费的时间就成了常数时间。比如：
| j |
0 |
1 |
2 |
3 |
4 |
5 |
| W[j] |
a |
b |
a |
c |
a |
b |
| F(j) |
0 |
0 |
1 |
0 |
1 |
1 |
当W[j]与T[j]不匹配的时候，设置j = F(j-1).
朱洪对KMP算法作了修改，他修改了KMP算法中的next函数，即求next函数时不但要求W[1,next(j)-1]=W[j-(next(j)-1)，j-1]，而且要求W[next(j)]W[j]，他记修改后的next函数为newnext。显然在模式串字符重复高的情况下，朱洪的KMP算法比KMP算法更加有效。
假设在执行正文中自位置 i 起“返前”的一段与模式的自右至左的匹配检查中，一旦发现不匹配（不管在什么位置），则去执行由W[m]与t[i]+d(x）起始的自右至左的匹配检查，这里x是字符t。它的效果相当于把模式向右滑过d(ti）一段距离。显然，若ti不在模式中出现或仅仅在模式末端出现，则模式向右滑过的最大的一段距离m。图1.1示出了执行BM算法时的各种情况。实线连接发现不匹配以后要进行比较的正文和模式中的字母，虚线连接BM算法在模式向右滑后正文和模式中应对齐的字母，星号表示正文中的一个字母。
public class StringMatching {
public static void main(String[] args) {
//暴力匹配算法
String str1 = "硅硅谷 尚硅谷你尚硅 尚硅谷你尚硅谷你尚硅你好";
String str2 = "尚硅谷你尚硅你";
int match = violenceMatch(str1, str2);
// System.out.println(match);
String s1= "BBC ABCDAB ABCDABCDABDE";
String s2 = "ABCDABD";
String s3 = "ABC";
int[] next = kmpNext("ABCDABD");//[0,1]
int res = kMP(s1, s2, next);
System.out.println(Arrays.toString(next));
System.out.println(res);
}
/*暴力匹配算法*/
public static int violenceMatch(String str1,String str2){
char[] s1 = str1.toCharArray();
char[] s2 = str2.toCharArray();
int i=0;//索引指向s1
int j = 0;//索引指向s2
while (i//匹配不越界
if (s1[i] ==s2[j]){//匹配成功
i++;
j++;
}else {//不成功
i = i -(j-1);
j=0;
}
}
//判断是否匹配成功
if (j==s2.length){
return i-j;
}else {
return -1;
}
}
/*获取到一个字符串的部分匹配值*/
public static int[] kmpNext(String dest){
/*保存部分匹配值*/
int[] next = new int[dest.length()];
next[0] = 0;//如果字符串长度为1；部分匹配值是0；
for (int i = 1 ,j=0; i ) {
//当不相等时需要从j-1获取新的j
/*直到发现dest.charAt(i) == dest.charAt(j)退出*/
while (j>0 &dest.charAt(i) != dest.charAt(j)){
j=next[j-1];//kmp算法的基础
}
if (dest.charAt(i) == dest.charAt(j)){
j++;
}
next[i] =j;
}
return next;
}
/*KMP算法查找字符最早出现的位置*/
public static int kMP(String str1,String str2,int[] next){
for (int i = 0 ,j=0; i ) {
/*需要考虑str1.charAt(i) ！=str2.charAt(j)时*/
while (j>0&&str1.charAt(i)!=str2.charAt(j)){
j=next[j-1];
}
if (str1.charAt(i) ==str2.charAt(j)){
j++;
}
if (j==str2.length()){
return i - j + 1;
}
}
return -1;
}
}