代码随想录二刷第八天 | 28. 实现 strStr()、459.重复的子字符串

28. 实现 strStr()

思路

KMP算法，实现方式为next数组初始化为0，不减一

代码

时间复杂度：O(m + n) 空间复杂度：O(m)

class Solution {
    public int strStr(String haystack, String needle) {
        if(needle.length() == 0) return 0;
        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++){
            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 static 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(i) != s.charAt(j)){
                j = next[j - 1];
            }
            if(s.charAt(i) == s.charAt(j)){
                j++;
            }
            next[i] = j;
        }
    }
}

459.重复的子字符串

思路

KMP算法+移动匹配。abcabc+abcabc,去掉开头和结尾，在其中找abcabc

代码

时间复杂度：O(m + n) 空间复杂度：O(m)

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        return kmp(s+s, s);
    }

    private boolean kmp(String str, String pattern){
        int[] next = new int[pattern.length()];
        next[0] = 0;
        int j = 0;
        for(int i = 1; i < pattern.length(); i++){
            while(j > 0 && pattern.charAt(i) != pattern.charAt(j)){
                j = next[j - 1];
            }
            if(pattern.charAt(i) == pattern.charAt(j)){
                j++;
            }
            next[i] = j;
        }

        j = 0;
        for(int i = 1; i < str.length() - 1; i++){
            while(j > 0 && str.charAt(i) != pattern.charAt(j)){
                j = next[j - 1];
            }
            if(str.charAt(i) == pattern.charAt(j)){
                j++;
            }
            if(j == pattern.length()){
                return true;
            }
        }

        return false;
    }
}