（1）BF 暴力算法

        /*
        * 一个一个字符比较，比较到最后都还是不相等的，就在A串下标+1，再次一个一个字符比较
        * */

（2）RK 暴力的优化，伪hash算法

        /*
        * 截取A串进行hashcode，B串进行hashcode，判断是否相等，不等就A串下标加1再次截取进行hashcode
        * 这样其实还是和暴力没啥区别
        * 自定义hash算法：
        *       把B串的每个字符的编码进行相加，得到结果作为hash值，然后A串也是把相同数量的字符的编码进行相加
        *       判断最后的hash值是否相同，相同的话再一个一个字符比较（因为这种方法很容易hash冲突）
        *       如果值不同，A传的hash值只需要减去第一个字符的编码，再加上新字符的编码，即可得到新的hash值
        * */

（3）BM算法
（3.1）坏字符规则

（3.2）好后缀规则

（4）KMP算法

//字符串搜索-----试题常见
/*
* 给定两个字符串A、B，判断B在A中是否存在，存在返回A中的下标，不存在返回-1
* 如：A：ABCABCAABCABCD
*    B：ABCABCD
* 返回值7
* 就是indexOf
* */
public class P43 {

    //KMP算法
    /*
    * 前缀：字符串A和B，A=B+S，S非空，则B为A的前缀
    * 后缀：A=S+B，S非空，则B为A的后缀
    * PMT值：前缀集合和后缀集合的交集，最长元素的长度
    *       假如串是ABCA，前缀有A、AB、ABC，后缀有A、CA、BCA，PMT值就是1
    *       假如串是ABC，前缀有A、AB，后缀有B、BC，PMT值就是0，没有交集
    *       找交集是为了移动，如
    *           BCADBCABCABCD
    *           BCADBCD
    *           这时是A和D不同，然后BCADBCD的前缀和BCADBCA的后缀的交集是BC，就可以移动为
    *           BCADBCABCABCD
    *               BCADBCD
    *           前缀移动到后缀位置
    *           交集长度是2，相当于把B串的2下标移动到那个A串不匹配的下标，就对齐了（最好找找网上的图示或视频，这里文字不好表示）
    * 部分匹配表：PMT值的集合，字符串的所有前缀的PMT值
    * prefix：每一个下标位置对于一个PMT值，组成的数值
    * next：prefix向右移一个下标位置，组成next数组
    * */

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

    //第一个参数是A串，第二个参数是B串，第三个参数是next数组，含有PMT值
    public static int search(char[] str, char[] pattern, int[] next){
        int i = 0;
        int j = 0;

        while(i < str.length && j < pattern.length){
            //j是有可能-1的，next[0]就是-1
            if(j == -1 || str[i] == pattern[j]){        //判断字符是否相等，相等就两个串的下标都加1再比较
                i++;
                j++;
            }else{
                j = next[j];
            }
        }

        if(j == pattern.length){
            return i - j;
        }else{
            return -1;
        }
    }
    /*
    * 过程分析
    * A串：ABCABCAABCABCD
    * B串：ABCABCD
    * next数组是[-1, 0, 0, 0, 1, 2, 3]
    * 先 i=0，j=0，进入while
    * str[0] == pattern[0]，进入分支，i=1，j=1
    * str[1] == pattern[1]，进入分支，i=2，j=2
    * str[2] == pattern[2]，进入分支，i=3，j=3
    * str[3] == pattern[3]，进入分支，i=4，j=4
    * str[4] == pattern[4]，进入分支，i=5，j=5
    * str[5] == pattern[5]，进入分支，i=6，j=6
    * str[6] != pattern[6]，进入else，i=6，j=next[6]=3，即如下所示
    * A串：ABCABCAABCABCD
    * B串：   ABCABCD
    * str[6] == pattern[3]，进入分支，i=7，j=4
    * str[7] != pattern[4]，进入else，i=7，j=next[4]=1，即如下所示
    * A串：ABCABCAABCABCD
    * B串：      ABCABCD
    * str[7] != pattern[1]，进入else，i=7，j=next[1]=0，即现在的对齐状态如下所示
    * A串：ABCABCAABCABCD
    * B串：       ABCABCD
    * str[7] == pattern[0]，进入分支，i=8，j=1
    * str[8] == pattern[1]，进入分支，i=9，j=2
    * str[9] == pattern[2]，进入分支，i=10，j=3
    * str[10] == pattern[3]，进入分支，i=11，j=4
    * str[11] == pattern[4]，进入分支，i=12，j=5
    * str[12] == pattern[5]，进入分支，i=13，j=6
    * str[13] == pattern[6]，进入分支，i=14，j=7
    * 退出while
    * j==B串长度，返回 i-j即14-7=7
    * */

    //构造next数组，其实就是PMT右移，因为prefix就是PMT数组，而next就是prefix全部右移的结果
    //第一个参数是B串，第二个参数是空数组
    public static void getNext(char[] pattern, int[] next){
        //因为是要求前缀和后缀的交集，而前缀就是不含最后一个字符，后缀就是不含第一个字符
        //即 abcdefg
        //    tuvwxyz   这样的对齐就是最初状态
        //  -1
        //可以看看下方的注释说明
        next[0] = -1;
        int i = 0;
        int j = -1;

        while(i < pattern.length){
            if(j == -1){
                i++;
                j++;
            }else if(pattern[i] == pattern[j]){     //就是判断上面注释例子的 b 是否等于 t
                i++;
                j++;
                next[i] = j;        //相等就是有交集，看看交集长度就是j
            }else{
                j = next[j];
            }
        }
    }

    /*
    * 假如pattern是ABCABCD
    * x串：ABCABCD
    * y串： ABCABCD
    * next[0]=-1
    * i是x串的0下标
    * j是y串的-1下标，对应x串的A
    * 进入while，j==-1，这是i=1，j=0，即x串的B、y串的A
    * x串的B != y串的A，所以走else，j=next[0]=-1，i还是1
    *
    * j==-1，这是j=0，i=2，即如下所示
    * x串：ABCABCD
    * y串：  ABCABCD
    * 又不相等了，j=next[0]=-1
    * 再次进入 j==-1分支，这是j=0，i=3，即
    * x串：ABCABCD
    * y串：   ABCABCD
    *
    * 然后pattern[i] == pattern[j]，大家都右移下标，i=4，j=1，并记录next[4]=1
    * 这里为什么是先加加，再记录交集长度呢？说过了，这是next数组，PMT数组右移
    * 也就是prefix[3]=1，即x串的3下标A字符的交集长度（PMT值）是1，所以next就是next[4]=1
    *
    * pattern[4] == pattern[1]，再次进入分支，这时 i=5，j=2，next[5]=2
    * pattern[5] == pattern[2]，再次进入分支，这是 i=6，j=3，next[6]=3
    *
    * 然后pattern[6] != pattern[3]，j=next[3]=0，没对next[3]赋值过，是初始化就是0，i=7
    * 退出while
    * next数组 [-1, 0, 0, 0, 1, 2, 3]，也可以推断出prefix数组 [0, 0, 0, 1, 2, 3, 0]
    * */
}