字符串搜索

给定两个字符串A、B，判断B在A中是否存在,存在返回A中的下标,不存在返回-1
例:
A: ABCABCAABCABCD
B: ABCABCD
返回值:7

解法一：调用API，String的indexOf方法

private static int indexOfStr_i(String str, String sub) {
    return str.indexOf(sub);
}

解法二：暴力破解

// 暴力破解
private static int bf(String str, String pattern) {
    int len_str = str.length();//主串的长度信息
    int len_sub = pattern.length();//子串的长度信息
    int i = 0;//主串开始位置
    int j = 0;//子串开始位置
    while(i<len_str && j<len_sub) {
        if(str.charAt(i) == pattern.charAt(j)) {//如果相等，两者同时向后走，i++,j++
            i++;
            j++;
        }
        else {//不相等  i回退到i-j+1    j回退开始位置0
            i = i-j+1;//i-j是这一趟的开始位置    这一趟的下一个位置：i-j+1
            j = 0;
        }
    }
    //此时while循环退出   两种情况，要么i走出范围   要么j走出范围
    if(j >= len_sub) {//如果子串的j走出范围，找到了，返回i-j
        return i-j;
    }
    else {//否则没有找到，匹配失败，返回-1
        return -1;
    }
}

BF算法的问题效率太低 ，时间复杂度是O（n*m）

解法三：KMP算法-KMP详解

public class stringSearch {
    public static void main(String[] args) {
        String str = "ABCABCAABCABCD";
        String pattern = "ABCABCD";
        int[] next = new int[pattern.length()];
        getNext(pattern.toCharArray(), next);
        int i = search(str.toCharArray(), pattern.toCharArray(), next);
        System.out.println(Arrays.toString(next));
        System.out.println(i);//kmp
    }
    private static void getNext(char[] pattern, int[] next) {
        next[0] = -1;
        int i = 0, j = -1;
        while (i < pattern.length) {
            if(j == -1) {
                j++;
                i++;
            }else if (pattern[i] == pattern[j]) {
                i++;
                j++;
                next[i] = j;
            }else {
                j = next[j];
            }
        }
    }
    private static int search(char[] str, char[] pattern, int[] next) {
        int i = 0, j = 0;
        while (i < str.length && j < pattern.length) {
            if (str[i] == pattern[j] || j == -1) {
                i++;
                j++;
            }else {
                j = next[j];
            }
        }
        if (j == pattern.length) {
            return i - j;
        }else {
            return -1;
        }
    }
}