代码随想录算法训练营第八天-28实现 strStr() 、459重复的子字符串

前言
状态：28 暴力（应为 KMP）、459 暴力（KMP 不会）
更新

1	24-05-29 初始记录

初步题解

28 实现 strStr()

题目链接：(https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/description/)

public class LE28 {  
    public static void main(String[] args) {  
        Scanner scanner = new Scanner(System.in);  
        String haystack = scanner.nextLine();  
        String needle = scanner.nextLine();  
        System.out.println(strStr(haystack, needle));  
    }  
  
    /**  
     * 思路：一个指针针对haystack遍历，一个指针针对needle遍历  
     * 当指针指过的路径相等，输出两者的差（即初始相等的指针位置）  
     * 当指向元素不同，haystack指针指向初始对比的下一个，needle指针重置  
     */  
    public static int strStr(String haystack, String needle) {  
        int j = 0;  
        for (int i = 0; i < haystack.length(); i++) {  
            if (haystack.charAt(i) == needle.charAt(j)) {  
                if (j == needle.length() - 1) {  
                    return i - j;  
                }  
                j++;  
            } else {  
                i = i - j;  
                j = 0;  
            }  
        }  
        return  -1;  
    }  
}

459 重复的子字符串

题目链接：(https://leetcode.cn/problems/repeated-substring-pattern/description/)

（虽然讲了 KMP 应该就用 KMP，但是不会）

// 暴力求解
public class LE459 {  
    public static void main(String[] args) {  
        Scanner scanner = new Scanner(System.in);  
        String nextLine = scanner.nextLine();  
        System.out.println(repeatedSubstringPattern(nextLine));  
    }  
  
    public static 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;  
    }  
}

看讲解

28 实现 strStr()

题目链接/文章讲解/视频讲解：(https://programmercarl.com/0028.实现strStr.html)

本题应该用 KMP 思路，这个算法主要用在字符串匹配上。KMP 的经典思想就是:当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。

/**  
 * 思路：使用KMP算法。  
 * 之前双指针移动，不相等haystack的指针返回到初始匹配位置的下一位（暴力求解）  
 * 现在使用KMP算法，不相等移动到next表中标记的位置。  
 * 所以现在的关键就在于next表的计算：  
 * 1.初始化  
 * 2.当前后缀不相等时的思路（回退）  
 * 3.当前后缀相等时的思路（继续后移）  
 * 内部相当于也进行了KMP
 */  
public static int strStr1(String haystack, String needle) {  
    // 获取Next表  
    int[] ints = new int[needle.length()];  
    int[] next = getNext(ints, needle);  
  
    int j = 0;  
    if (needle.length() == 0) {  
        return -1;  
    }  
    for (int i = 0; i < haystack.length(); i++) {  
        // 不相等, j回退  
        while (j != 0 && haystack.charAt(i) != needle.charAt(j)) {  
            j = next[j - 1];  
        }  
        // 相等  
        if (haystack.charAt(i) == needle.charAt(j)) {  
            // 完全匹配，返回下标  
            if (j == needle.length() - 1) {  
                return i - j;  
            }  
            j++;  
        }  
  
    }  
    return  -1;  
}  
  
/**  
 * 获取next表，例：  
 * a a b a a f  
 * 0 1 0 1 2 0 * * 1.初始化  
 * 2.当前后缀不相等时的思路（回退）  
 * 3.当前后缀相等时的思路（继续后移）  
 *  
 * @param next 返回的next数组  
 * @param s 要求的字符串  
 * @return next数组  
 */  
private static int[] getNext(int[] next, String s) {  
    // 初始化 两个指针i和j，j指向前缀末尾位置(同时也是之前最长相等的前后缀长度)，i指向后缀末尾位置(随着字符串长度递增，递增)。  
    // 刚刚初始化时，字符串为a，所以j = 0  
    int j = 0;  
    next[0] = j;  
  
    // 这里i从1开始，没有搞懂(因为初始位置一定为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;  
    }  
    return next;  
}

459 重复的子字符串

题目链接/文章讲解/视频讲解：(https://programmercarl.com/0459.重复的子字符串.html)

/**  
 * KMP思路  
 * 如果这个字符串是由重复子串组成的，那么字符串长度-最长相等前后缀就为重复子串的长度  
 * 反过来说，如果一个字符串的最长相等前后缀与长度的差值（即可能是重复子串长度的这个值）能被字符串长度整除，那么就说明这个字符串是由重复子串组成的  
 * 但是这个反过来说。需要证明。（虽然画了几种情况都是这样）  
 *  
 * KMP复习：  
 * 1.初始化  
 * 2.不相等的情况  
 * 3.相等的情况  
 */  
public static boolean repeatedSubstringPattern1(String s) {  
    int[] next = getNext(s);  
    // 这里除了上面说的条件之外，还需要加上next[len - 1] != -1, 这说明字符串有最长相同的前后缀（就是字符串里的前缀子串和后缀子串相同的最长长度）  
    return next[s.length() - 1] != 0 && s.length() % (s.length() - next[s.length() - 1]) == 0;  
}  
  
private static int[] getNext(String s) {  
    int j = 0;  
    int[] next = new int[s.length()];  
    next[j] = 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;  
    }  
  
    return next;  
}