String Search

给定两个字符串A、B，判断B在A中是否存在，存在返回A中的下标，不存在返回-1

例:A:ABCABCAABCABCD
B:ABCABCD

返回值:7

public class KMP {
    public static void main(String[] args) {
        String str1 = "ABCABCAABCABCD";
        String strPattern = "ABCABCD";
        int[] next = new int[strPattern.length()];
        getNext(strPattern.toCharArray(),next);
        int i = search(str1.toCharArray(),strPattern.toCharArray(),next);
        System.out.println(Arrays.toString(next));
        System.out.println(i);
        System.out.println(str1.indexOf(strPattern));
    }
    static int search(char[] str,char[] pattern,int[] next){
        int I=0;
        int j=0;

        while(i<str.length&&j<pattern.length){
            if (j==-1||str[i]==pattern[j]){
                I++;
                j++;
            }else {
                j=next[j];
            }
        }
        if (j==pattern.length){
            return i-j;
        }else {
            return -1;
        }
    }
    //pattern:需要比较的字符串
    static void getNext(char[] pattern,int[] next){
        next[0]=-1;
        int i=0,j=-1;
        while(i<pattern.length){
            if (j==-1){
                I++;
                j++;
            }else if (pattern[i]==pattern[j]){
                i++;j++;
                next[i] = j;
            }else {
                j=next[j];
            }
        }
    }
}

String Search

原文：https://www.cnblogs.com/cfs322/p/15110340.html