5.6 KMP模式匹配算法
什么是KMP？
三个科学家D.E.Knuth、 J.H.Morris 和V.R.Pratt，以他们的姓氏命名的
为什么要用KMP算法？
因为暴力匹配效率太低
比如我们要在主串中匹配子串ABCD，这很简单对吧，常规的思路就是一位一位的匹配（这个思路就是暴力匹配算法）
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-b9kx80Ep-1637065551742)(C:/Users/Jack/AppData/Roaming/Typora/typora-user-images/image-20211116093132194.png)]
如果对不上了，我们让子串往后移动
上面这种思路可以用代码来实现
/** * 暴力破解法 * @param ts 主串 * @param ps 模式串 * @return 如果找到，返回在主串中第一个字符出现的下标，否则为-1 */ public static int bf(String ts, String ps) { char[] t = ts.toCharArray(); char[] p = ps.toCharArray(); int i = 0; // 主串的位置 int j = 0; // 模式串的位置 while (i < t.length && j < p.length) { if (t[i] == p[j]) { // 当两个字符相同，就比较下一个 i++; j++; } else { i = i - j + 1; // 一旦不匹配，i后退 j = 0; // j归0 } } if (j == p.length) { return i - j; } else { return -1; } }
上面的程序没问题，只能说不够好！
主串匹配失败的位置除了第一个A之外再也没有A了，我们为什么知道主串前面只有一个A？因为前三个已经匹配过了啊！它们都是匹配的。
我们可以这样保存i不动，移动j
KMP算法的思想就是利用已经部分匹配的有效信息，保持i指针不回溯，通过修改j指针，让子串尽量的移动到有效的位置！
再详细的可以观看这篇文章，写的很好！
我就不更了，日后在更
（原创）详解KMP算法 - 孤~影 - 博客园 (cnblogs.com)
KMP模式匹配算法实现
/*通过计算返回子串T的next数组。*/ void get_ next ( String T, int *next ) { int i,j; i=1; j=0; next[1]=0; while ( i<T[0]) /*此处T[0]表示串T的长度*/ { if (j==0 11 T[i]== T[j]) /* T[i]表示后缀的单个字符，*/ /* T[j]表示前缀的单个字符*/ { ++i; ++j; next[i]=j; } else j= next[j]; /*若字符不相同，则j值回溯*/ } }
/*返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数返回值为0。*/ /* T非空，1SposSStrLength (s)。*/ int Index KMP (String s, String T, int pos ) { int i= pos;/*i用于主串S当前位置下标值，若pos不为1, */ /*则从pos位置开始匹配*/ int j= 1; /*j用于子串T中当前位置下标值*/ int next[255] ; /*定义一next数组*/ get_ next(T, next); /*对串工作分析，得到next数组*/ while(i<= S[0] &j<= T[0]) /*若i小于S的长度且j小于T的长度时，*/ /*循环继续*/ { if (j==0日1 S[i]== T[j]) /*两字母相等则继续，与朴素算法增加了*/ /*j=0判断*/ ++i; ++j; else /*指针后退重新开始匹配★/ { j = next[j]; /* j退回合适的位置，i值不变*/ } if(j > T[0] ) return i-T[0] ; else return 0; }
5.7总结
串是由零个或多个字符组成的有限序列，又名字符串。本质上是一种线性表的扩展，相对于线性表关注一个个元素来说，串这种结构更多的是关注它子串的应用问题，如查找、替换等操作。现在的高级语言都有针对串的函数可以调用，我们在使用这些函数的时候，同时也应该要理解它当中的原理，以便于再碰到复杂问题时，可以更灵活的使用
