找出字符中的第一个匹配项的下标

题目：实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

暴力枚举

思路：两层循环

class Solution {
    public int strStr(String haystack, String needle) {
        for(int i = 0;i<haystack.length();i++){
            int fast = i;
            int len = 0;
            for(int j = 0;j<needle.length();j++){
                if(fast < haystack.length() && haystack.charAt(fast) == needle.charAt(j)){
                    fast++;
                    len++;
                }else{
                    break;
                }
            }
            if(len == needle.length()){
                return i;
            }
        }
        return -1;
    }
}

时间复杂度是O(m*n)

KMP

思路：先求出目标字符串的前缀表，然后遍历字符串，遇到不相同的字符的时候，指向模版字符串的指针回退指定位置（依据前缀表），然后继续匹配

class Solution {
    public int strStr(String haystack, String needle) {
        if(needle.length() > haystack.length()){
            return -1;
        }
        int[] next = new int[needle.length()];
        getNext(next,needle);
        int j = 0;// 指向模版串
        for(int i = 0;i<haystack.length();i++){
            // i和j指向的字符不同的时候 j直接跳到指定位置（不一定是从头开始）重新开始匹配
            while(j > 0 && needle.charAt(j) != haystack.charAt(i)){
                    j = next[j - 1];
            }  
            // 相同则一起往前走
            if(needle.charAt(j) == haystack.charAt(i)){
                j++;
            }
            // 走完模版字符串了，就可以返回下标了
            if(j == needle.length()){
                return i - needle.length() + 1;
            }
        }
        return -1;
    }

    private void getNext(int[] next,String needle){
        // 初始化数组第一个元素
        next[0] = 0;
        int j = 0;// 前缀末尾位置
        for(int i = 1;i<needle.length();i++){// i 后缀末尾位置
           // 前后缀不相同的情况
            while(j > 0 && needle.charAt(j) != needle.charAt(i)){
                j = next[j - 1];// 这里为什么不是 j = j-1呢，因为当前j-1保存的值就是最长的前缀相等的元素长度，既然前面是相同的，又因为现在的j指向的位置和i指向的位置不相等，所以可以直接将j跳到指定位置，而不是一步一步退
            }
            // 前后缀相同的情况
            if(needle.charAt(j) == needle.charAt(i)){
                // i 和 j 都往前走一步，这里i在循环里面会+1，就不用单独i++了
                j++;
            }
            // 更新next数组
            next[i] = j;
        }
    }
}

时间复杂度是O(m+n)

这里还有个小小的疑惑，为什么while一定要在if前面？

重复的子字符串

题目：给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。

记录一下，后面二刷的时候在来看看，这里思路还是有点模糊

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        int len = s.length();
        int[] next = new int[s.length()];
        getNext(next,s);
        if(next[len-1] != 0 && len % (len - next[len-1]) == 0){
            return true;
        }
        return false;
    }

    private void getNext(int[] next,String s){
        int j = 0;
        next[0] = 0;
        for(int i = 1;i<s.length();i++){
            while(j > 0 && s.charAt(j) != s.charAt(i)){
                j = next[j - 1];
            }
            if(s.charAt(j) == s.charAt(i)){
                j++;
            }
            next[i] = j;
        }
    }
}

时间复杂度是O(n)

总结

这两个题目都是KMP算法的经典题目，重点是如何计算出next数组。