[LeetCode]28. Implement strStr()

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Example 1:
Input: haystack = "hello", needle = "ll" Output: 2 Example 2:
Input: haystack = "aaaaa", needle = "bba" Output: -1 Clarification:
What should we return when needle is an empty string? This is a great question to ask during an interview.
For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf(). 需要注意边界条件，例如把正常逻辑全放到对haystack的循环体中，但haystack可能为空，逻辑将会走不到

public int strStr(String haystack, String needle) {
        char[] a1=haystack.toCharArray();
        char[] a2=needle.toCharArray();
        if(a2.length==0) return 0;
        for(int i=0;i<a1.length;i++){
            boolean flag=true;
            for(int j=0;j<a2.length;j++){
                if(i+j>=a1.length || a1[j+i]!=a2[j]) {
                    flag=false;
                    break;
                }
            }
            if(flag) return i;
        }
        return -1;
}

上面的复杂度是o(n*m),在某些重复串较多的情况下，时间不理想，上面的使用暴力匹配的思想，可以用KMP算法来优化

KMP的原理和回文串的马拉车算法类似，利用已有的信息去除一些无用的判断

例如

P：ABCABC D……

T：ABCABC E

这个时候判断

ABCABC D……

ABCAB CE

是没有意义的

因为当需要回溯找串的时候需要保证

23456==12345

123456 7……

12345 68

而上面的关系完全取决于T自己，可以提前计算，也就是说我们在发生不匹配的时候，可以直接确定需要相对移动的值，不需要完全回溯

我们的问题转化为

T： ABCABCABCABC Y

T'：ABCABCABCABC

在Y位上发生不匹配后，确定所有的k位满足T’的前k位等于后k位

这样看起来储存k位置的是个二维结构，

看上面的例子，这时候看起来需要回溯的情况为[ABC,ABCABC,ABCABCABC]

有一个不容易发现的问题

{n1 n1}

{n2 n2}

当k1>k2时，k2一定是k1的子串，这样就能形成线性结构，这就是next数组，求next数据是一个动态规划的过程

我们定义next[k]是k位置之前前缀和后缀重合最大的长度

public int strStr(String haystack, String needle) {
    char[] a1=haystack.toCharArray();
    char[] a2=needle.toCharArray();
    int l1=a1.length;
    int l2=a2.length;
    if(l2==0) return 0;
    int[] next=new int[l2];
    for(int i=2;i<l2;i++){
        int t=next[i-1];
        while(t!=-1){
            if(a2[t]==a2[i-1]) {
                next[i]=t+1;
                break;
            }
            else {
                if(t==0) break;
                t=next[t];
            }
        }
    }
    int i=0;
    int j=0;
    while(i<l1 && j<l2){
        if(a1[i]==a2[j]){
            i++;
            j++;
        }else{
            if(next[j]!=0){
                j=next[j];
            }else{
                i=i-j+1;
                j=0;
            }
        }
    }
    return j==l2?i-j:-1;
}