Kmp算法习题演练

KMP算法是一种改进的字符串匹配算法,核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。

例题： 在字符串str1中匹配str2

str1=“abbbcchabbbccikkkabciabckkk”

str2=“abciabc”

主函数类：

package Supplement;

import java.util.List;
import java.util.Stack;

public class Main {

    public static void main(String[] agrs){
        /**
         * kmp算法
         * 匹配字符串str1中是否含有字符串str2
         * */
        Practice practice = new Practice();
        String str1 = "abbbcchabbbccikkkabciabckkk";
        String str2 = "abciabc";
        int index = practice.getIndexOf(str1,str2);
        System.out.println("开始匹配的位置是："+ index);
    }

}

实现类：

package Supplement;

import org.omg.PortableInterceptor.SYSTEM_EXCEPTION;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Practice {
    /**
     * kmp算法
     * 求字符串str1 中是否包含字符串str2
     * ***/
    //kmp算法
    public int getIndexOf(String str1,String str2){
        if(str1 == null || str2 == null || str1.length() <1 || str2.length() < 1) return -1;
        char[] arr1 = str1.toCharArray();
        char[] arr2 = str2.toCharArray();
        int index1 = 0; //数组1匹配的位置
        int index2 = 0; //数组2匹配的位置
        int[] str2Next = getNextArray(arr2); //数组2的重复部分的小标
        while (index1 < arr1.length && index2 < arr2.length){
            if(arr1[index1] == arr2[index2]) { //匹配成功
                index1++;
                index2++;
            }else if(str2Next[index2] == -1){
                index1++;  //arr2已经回溯到开头依旧无法匹配上，arr1放弃已经匹配成功匹配的部分，从后面重新开始
            }
            else index2 = str2Next[index2]; //回溯之前匹配成功的部分，将arr1已经匹配成功的部分舍弃
        }
        return  index2==arr2.length?index1-index2:-1; //匹配成功，则index1-index2的结果就是开始匹配的位置。否则返回-1匹配失败
    }
    
    //求str2局部匹配信息
    public int[] getNextArray(char[] arr2){
        if(arr2.length == 0) return new int[]{-1}; //0位置设置为-1；
        int [] next = new int[arr2.length];
        next[0] = -1;  //0位置人为设置为-1；
        next[1] = 0; //1位置认为设置为0；
        int i = 2;
        int cn = 0;
        while (i 0) cn = next[cn]; //没匹配上，cn往前跳
            else next[i++] = 0;  //全没有匹配上，该节点为0
        }
        return next;
    }
}

主方法 getIndexOf（） 部分代码图解：