java实现一个kmp算法

1、什么是KMP算法

      Kmp 算法是由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，改进字符串匹配的算法；

      Kmp 算法的核心是利用匹配失败的信息，尽量减少模式串与主串的匹配次数，以达到

      快速匹配的目的；

      Kmp 算法的时间复杂度是O(m+n)，m=模式串的长度，n=主字符串的长度

2、示例代码

/*** Kmp算法练习1:* 1、什么是Kmp算法？* Kmp 算法是由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，改进字符串匹配的算法；* Kmp 算法的核心是利用匹配失败的信息，尽量减少模式串与主串的匹配次数，以达到快速匹配的目的；* Kmp 算法的时间复杂度是O(m+n)，m=模式串的长度，n=主字符串的长度***/
public class KMPDemo01 {/**** @param str 主字符串* @param p  要查找的字符串，即模式串* @return*/public int kmp(String str,String p){if(str == null || "".equals(str.trim()) || p == null || "".equals(p.trim())){return -1;}int[] next = new int[p.length()];int i=0,j=0;/*** 1、计算模式串的next数组*/next(next,p);/*** 匹配过程*/while (i<str.length() && j<p.length()){//当主字符串与模式串的字符匹配时，主字符串坐标i和模式字符串坐标j同时增加//否则，模式字符串坐标j回溯if(j == -1 || str.charAt(i) == p.charAt(j)){i++;j++;}else {/*** j 回退，返回上一个满足条件的位置*/j = next[j];}}if((i - p.length()) >= 0){return i - p.length();}return -1;}/*** next数组的计算* 数组 next 保存每次遇到字符不一样的上一个的位置* 对于模式串p的每个位置j，next[j]表示p[0,j-1]的最长相等前后缀子串的长度** @param next* @param p*/private void next(int[] next,String p){int j = 0;int k = -1;next[0] = -1;while (j< p.length() - 1){if(k == -1 || p.charAt(k) == p.charAt(j)){k++;j++;if(p.indexOf(k) == p.indexOf(j)){next[j] = next[k];}else {next[j] = k;}}else {/*** k回退，获取上一步的k*/k = next[k];}}}public static void main(String[] args) {KMPDemo01 kmp = new KMPDemo01();String str = "12324abc567";String p = "ab";int index = kmp.kmp(str,p);System.out.println(" ****** index ****** "+index);}}