[数据结构与算法]KMP算法代码实现

求子串出现的位置

package com.byc.day1;

import java.util.Arrays;

public class KMP {
    public static void main(String[] args) {
        String A = "aabaabaaxaabaabayaaabaabaaaqqq";
        String B = "aabaabaaa";
        System.out.println(A.substring(18));
        int[] indexArray = getIndexArray(B.toCharArray());
        System.out.println(getIndexOfSubStr2(A.toCharArray(),B.toCharArray(),indexArray));
    }




    
    public static int[] getIndexArray(char[] pattern){
        int[] indexArray = new int[pattern.length];
        for (int i = 0; i < indexArray.length; i++) {
            indexArray[i] = 0;
            int subRightIndex = i - 1;
            int temp = 0;
            for (int j = i - 2; j >= 0; j--) {
                if (pattern[subRightIndex]==pattern[j]){
                    temp ++;
                    subRightIndex--;
                }else {
                    subRightIndex = i - 1;
                    temp = 0;
                    if (pattern[subRightIndex]==pattern[j]){
                        temp ++;
                        subRightIndex--;
                    }
                }
            }
            indexArray[i] = temp;
        }
        return indexArray;
    }





    public static int getIndexOfSubStr2(char[] A,char[] B,int[] patternIndex){
        for (int i = 0,j = 0; i < A.length; i++) {
            while (j < B.length){
                if (A[i] != B[j]) {
                    j = patternIndex[j];
                    if (j!=0){
                        i--;
                    }
                    break;
                } else {
                    j++;
                    if (j==B.length){
                        return i - j + 1;
                    }
                    break ;
                }
            }
        }
        return -1;
    }

    
    // 初始想法，可以得到结果，但是这个做法不行，增加了很多运算量
    @Deprecated
    public static int[] getIndexArray2(char[] pattern){
        int[] indexArray = new int[pattern.length];
        for (int i = 0; i < indexArray.length; i++) {
            indexArray[i] = -1;
        }
        // i表示，坏字符出现的位置
        for (int i = 0; i < pattern.length; i++) {
            indexArray[i] = 0;
            int j = 0;
            // 子串的最后一个字符
            outer:for (;j<i-1; j++){
                // 某个字符相等了
                if (pattern[j]==pattern[i-1]){
                    int x = 1;
                    for (;x<=j;x++){
                        if (pattern[j-x]!=pattern[i-1-x]){
                            continue outer;
                        }
                    }
                    indexArray[i] = j+1;
                }
            }
            System.out.println(indexArray[i]);
        }
        return indexArray;
    }
}