LeetCode28-Implement-strStr

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;
}