KPM算法思想及实现

KPM算法思想及实现

一、比较暴力算法和KMP算法

1、暴力算法：

双指针遍历主串和子串，当发现主串和子串不匹配时，双指针同时回溯

2、KMP算法：

双指针遍历主串和子串，当发现主串和子串不匹配时，通过比较子串的next数组只回溯子串指针，从而提高算法速度

二、next数组含义

next[j]=第j位字符前面的j-1位字符所组成的子串的最长公共前后缀长度

三、计算next数组

计算子串每个字符左子串的最长公共前后缀长度

四、算法实现

public class KMP {public static void main(String[] args) {String str="abcksljafkdshfjksd";String subs="sl";System.out.println(kmp(str,subs));}/*** 遍历比较字符串* @param str 主串* @param subs 子串* @return 子串在主串出现的第一个位置下标*/public static  int  kmp(String str,String subs){char[] subc=subs.toCharArray();                 //将子串转换成字符数组方便计算next数组int[] next=new int[subc.length];                //声明next数组getNext(subc,next);                             //计算next数组int i=0,j=0;                                    //双指针遍历主串和子串while(i<str.length()&&j<subs.length()){if(j==-1||str.charAt(i)==subs.charAt(j)){i++;j++;}else{j=next[j];                              //子串回溯}if(j==subs.length()){return i-j;                             //返回index下标}}return -1;}/*** 计算改变next数组（计算最长公共前后缀的值）* @param subc 子串* @param next next数组*/public static void getNext(char[] subc,int[] next){next[0]=-1;                                 //设置数组第一位为-1if(subc[1]==subc[0]){                      //判断子串第二位与第一位是否相等next[1]=1;                              //相等赋值为1，表明此时最长公共前缀为1}else{next[1]=0;                              //反之赋值为0}int i=2;                                    //从子串下标为2的位置开始计算int j=-1;                                   //此时j为next[0]的值while(i<subc.length){                       //遍历子串if(j==-1||subc[i-1]==subc[j]){          //判断上一个最长公共前后缀后的字符是否相等next[i++]=++j;                      //最长公共前后缀长度加一}else{j=next[j];                          //往前递归找上一个最长公共前后缀}}}}