代码随想录算法训练营Day09|28. 实现 strStr()、459.重复的子字符串

---

一、28. 实现 strStr()

题目描述： 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

本题是经典的字符串单模匹配的模型，因此可以使用字符串匹配算法解决，常见的字符串匹配算法包括暴力匹配、Knuth-Morris-Pratt 算法、Boyer-Moore 算法、Sunday 算法等。

1. 暴力匹配

让字符串 needle 与字符串 haystack 的所有长度为 m 的子串均匹配一次。

• 时间复杂度：$O(n?m)$
• 空间复杂度：$O(1)$

class Solution {
    public int strStr(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        for (int i = 0; i + m <= n; i++) {
            boolean flag = true;
            for (int j = 0; j < m; j++) {
                if (haystack.charAt(i + j) != needle.charAt(j)) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                return i;
            }
        }
        return -1;
    }
}

2. Knuth-Morris-Pratt 算法

当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。
视频链接： 帮你把KMP算法学个通透！（求next数组理论篇）和 帮你把KMP算法学个通透！（求next数组代码篇）

• 时间复杂度：$O(n?m)$
• 空间复杂度：$O(1)$

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

            if(s.charAt(i)==s.charAt(j+1)){
                j++;
            }
            next[i] = j;
        }
    }
    public int strStr(String haystack, String needle) {
        if(needle.length()==0){
            return 0;
        }

        int[] next = new int[needle.length()];
        getNext(next, needle);
        int j = -1;
        for(int i = 0; i<haystack.length();i++){
            while(j>=0 && haystack.charAt(i) != needle.charAt(j+1)){
                j = next[j];
            }
            if(haystack.charAt(i)==needle.charAt(j+1)){
                j++;
            }
            if(j==needle.length()-1){
                return (i-needle.length()+1);
            }
        }

        return -1;
    }
}

二、459.重复的子字符串

题目描述： 给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

1.枚举法

如果一个长度为 n 的字符串 s 可以由它的一个长度为 n′ 的子串 s′ 重复多次构成，那么：n 一定是 n′ 的倍数；s′ 一定是 s 的前缀；对于任意的 i∈[n′,n)，有 s[i]=s[i?n′]。

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(n)$

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        int n = s.length();
        for (int i = 1; i * 2 <=n; ++i) {
            if (n % i == 0) {
                boolean match = true;
                for (int j = i; j < n; ++j) {
                    if (s.charAt(j) != s.charAt(j - i)) {
                        match = false;
                        break;
                    }
                }
                if (match) {
                    return true;
                }
            }
        }
        return false;
    }
}

2.字符串匹配

将两个 s 连在一起，并移除第一个和最后一个字符。如果 s 是该字符串的子串，那么 s 就满足题目要求。

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        return (s + s).indexOf(s, 1) != s.length();
    }
}

3.KMP算法

class Solution {
    public boolean repeatedSubstringPattern(String s) {
       if (s.equals("")) return false;

       int len = s.length();
       // 原串加个空格（哨兵），使下标从1开始，这样j从0开始，也不用初始化了
       s = " " + s;
       char[] chars = s.toCharArray();
       int[] next = new int[len + 1];

       // 构造next 数组过程，j从0开始（空格），i从2开始
       for (int i = 2, j = 0; i <= len; i++) {
           // 匹配不成功，j回到前一位置next数组所对应的值
           while (j > 0 && chars[i] != chars[j + 1]) j = next[j];
           // 匹配成功，j往后移
           if (chars[i] == chars[j + 1]) j++;
           // 更新next数组
           next[i] = j;
       } 

       // 最后判断是否是重复的子字符串，这里next[len]即代表next数组末尾的值
       if (next[len] > 0 && len % (len - next[len]) == 0) {
           return true;
       } else {
           return false;
       }
    }
}

---

总结

以上就是今天学习的内容，KMP算法比较难理解，可以结合视频观看。