// @Title: 找出字符串中第一个匹配项的下标 (Find the Index of the First Occurrence in a String)
// @Author: qisiii
// @Date: 2024-09-13 21:52:01
// @Runtime: 1 ms
// @Memory: 40.3 MB
// @comment: KMP带注释版
// @flag: GREEN
class Solution {
    public int strStr(String haystack, String needle) {
        int[] next=buildNext(needle);
        for(int i=0,j=0;i<haystack.length();i++){
            while(j>0&&haystack.charAt(i)!=needle.charAt(j)){
                //冲突的时候，会去找next数组前一位的值
                j=next[j-1];
            }
            if(haystack.charAt(i)==needle.charAt(j)){
                j++;
            }
            if(j==needle.length()){
                return i-j+1;
            }

        }
        return -1;
    }

    private int[] buildNext(String needle){
        //最长公共前后缀的下一位（或者说最大公共前后缀的位数），初始值为0
        int prefixNext=0;
        int[] next=new int[needle.length()];
        //因为第一个字符串是首尾相继，因此最大公共前后缀的位数就是0.
        next[0]=prefixNext;
        //cur表明是后缀最后一位，即要比较的数
        //比较的逻辑也是先比较next[cur-1]和cur是否相等，相等的话公共前后缀的长度+1，cur的next数组值就是next[cur-1]+1
        //假如不等，就要找到前一位next数组的位置
        //比如aabaaf，假设cur为f的话，比较的就是b和f这两位
        for(int cur=1;cur<needle.length();cur++){
            while(prefixNext>0&&needle.charAt(cur)!=needle.charAt(prefixNext)){
                //这里作何分析？
                //虽然是在构建next数组，但本质上也是一个字符串匹配的过程,比如aabaaf,当b和f比较时，可以视作匹配串是aab，待比较串是aabaaf，b和f冲突了，我们会看aab的next数字的前一位的next数组值，视作不变量
                prefixNext=next[prefixNext-1];
            }
            if(needle.charAt(cur)==needle.charAt(prefixNext)){
                prefixNext++;
            }
            next[cur]=prefixNext;
        }
        return next;
    }
}

// @Title: 找出字符串中第一个匹配项的下标 (Find the Index of the First Occurrence in a String)
// @Author: qisiii
// @Date: 2024-09-13 16:40:03
// @Runtime: 1 ms
// @Memory: 40.4 MB
// @comment: 暴力
// @flag: RED
class Solution {
    public int strStr(String haystack, String needle) {
        for(int i=0;i<=haystack.length()-needle.length();i++){
            int k=0;
            for(int j=i;j<i+needle.length();j++,k++){
                if(haystack.charAt(j)!=needle.charAt(k)){
                    break;
                }
            }
            if(k==needle.length()){
                return i;
            }
        }
        return -1;
    }
}

// @Title: 找出字符串中第一个匹配项的下标 (Find the Index of the First Occurrence in a String)
// @Author: qisiii
// @Date: 2024-09-13 16:07:09
// @Runtime: 0 ms
// @Memory: 40.4 MB
// @comment: indexOf

// @flag: WHITE
class Solution {
    public int strStr(String haystack, String needle) {
        return haystack.indexOf(needle);
    }
}

// @Title: 找出字符串中第一个匹配项的下标 (Find the Index of the First Occurrence in a String)
// @Author: qisiii
// @Date: 2024-09-13 21:15:38
// @Runtime: 1 ms
// @Memory: 40.5 MB
// @comment: 重新理解KMP
// @flag: GREEN
class Solution {
    public int strStr(String haystack, String needle) {
        int[] next=buildNext(needle);
        for(int i=0,j=0;i<haystack.length();i++){
            while(j>0&&haystack.charAt(i)!=needle.charAt(j)){
                j=next[j-1];
            }
            if(haystack.charAt(i)==needle.charAt(j)){
                j++;
            }
            if(j==needle.length()){
                return i-j+1;
            }

        }
        return -1;
    }

    private int[] buildNext(String needle){
        int prefixNext=0;
        int[] next=new int[needle.length()];
        next[0]=0;
        for(int cur=1;cur<needle.length();cur++){
            while(prefixNext>0&&needle.charAt(cur)!=needle.charAt(prefixNext)){
                prefixNext=next[prefixNext-1];
            }
            if(needle.charAt(cur)==needle.charAt(prefixNext)){
                prefixNext++;
            }
            next[cur]=prefixNext;
        }
        return next;
    }
}

// @Title: 找出字符串中第一个匹配项的下标 (Find the Index of the First Occurrence in a String)
// @Author: qisiii
// @Date: 2024-04-14 13:50:49
// @Runtime: 1 ms
// @Memory: 40.5 MB
// @comment: kmp
// @flag: WHITE
class Solution {
    public int strStr(String haystack, String needle) {
        if(haystack.equals(needle)){
            return 0;
        }
        int[] next=new int[needle.length()];
        getNext(next,needle);
        int j=0;
        for(int i=0;i<haystack.length();i++){
            while(j>0&&haystack.charAt(i)!=needle.charAt(j)){
                j=next[j-1];
            }
            if(haystack.charAt(i)==needle.charAt(j)){
                j++;
            }
            if(j==needle.length()){
                return i-j+1;
            }
        }
        return -1;

    }
    /**
     * 初始化被匹配的字符串的前缀表
     */
    public void getNext(int[] next,String needle){
        int j=0;
        next[0]=0;
        for(int i=1;i<needle.length();i++){
            while(j>0&&needle.charAt(i)!=needle.charAt(j)){
                j=next[j-1];
            }
            if(needle.charAt(i)==needle.charAt(j)){
                j++;
            }
            next[i]=j;
        }   
    }
}