重复的子字符串 | LeetCode-459 | 字符串匹配 | KMP | 双指针

KMP练习题

---

LeetCode链接：459. 重复的子字符串

---

1.题目描述

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

示例 1:

输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。

示例 2:

输入: s = "aba"
输出: false

示例 3:

输入: s = "abcabcabcabc"
输出: true
解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)

提示：

• $1 <= s.length <= 10^4$
• s 由小写英文字母组成

2.题解

2.1 暴力解法

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        int n = s.length();  // 获取字符串的长度
        // 枚举可能的子串长度，最大长度为字符串长度的一半
        for(int i = 1; i <= n / 2; i++) {
            // 如果字符串长度能被子串长度整除，说明可能由该长度的子串重复构成
            if(n % i == 0) {
                int j;
                // 检查从索引 i 开始的字符是否和子串的字符匹配
                for(j = i; j < n; j++) {
                    // 如果当前字符与前面子串对应位置的字符不匹配，跳出循环
                    if(s.charAt(j) != s.charAt(j - i)) break;
                }
                // 如果 j 遍历到了字符串的末尾，说明整个字符串可以由子串重复构成
                if(j == n) return true;
            }
        }
        // 如果没有找到满足条件的子串，返回 false
        return false;
    }
}

2.2 KMP - 移动匹配

2.2.1 内置函数

class Solution {
    // 判断字符串 s 是否由一个子串重复组成
    public boolean repeatedSubstringPattern(String s) {
        // 将字符串 s 自身连接，并从索引 1 开始查找 s 的首次出现位置
        // 如果找到了且位置不等于 s 的长度，说明 s 是由一个子串重复组成
        return (s + s).indexOf(s, 1) != s.length();
    }
}

2.2.2 KMP实现

class Solution {
    // 判断字符串 s 是否由一个子串重复组成
    public boolean repeatedSubstringPattern(String s) {
        int n = s.length(); // 获取字符串 s 的长度
        String goal = s; // 保存原始字符串
        s = s + s; // 将字符串 s 自身连接，形成新的字符串
        int[] next = getNext(goal); // 生成目标字符串的前缀函数数组
        int j = 0; // 初始化匹配指针，用于遍历目标字符串

        // 遍历新的字符串 s，直到 n*2-1 位置
        for (int i = 1; i < n * 2 - 1; i++) {
            // 当前字符不匹配时，根据前缀函数回退 j
            while (j > 0 && s.charAt(i) != goal.charAt(j)) j = next[j - 1];
            // 如果字符匹配，增加 j
            if (s.charAt(i) == goal.charAt(j)) j++;
            // 如果 j 达到目标字符串的长度，表示找到了重复子串
            if (j == n) return true;
        }

        return false; // 如果没有找到符合条件的重复子串，返回 false
    }
    // 生成前缀函数数组
    public int[] getNext(String s) {
        int n = s.length(); // 获取字符串 s 的长度
        int[] next = new int[n]; // 初始化前缀函数数组
        int j = 0; // 前缀指针
        next[0] = 0; // 第一个字符的前缀长度为 0

        // 遍历字符串，从第二个字符开始
        for (int i = 1; i < n; i++) {
            while (j > 0 && s.charAt(i) != s.charAt(j)) j = next[j - 1];// 当当前字符不匹配时，回退前缀指针 j
            if (s.charAt(i) == s.charAt(j)) j++;// 如果字符匹配，前缀长度增加
            next[i] = j;// 记录当前字符的前缀长度到 next 数组
        }
        
        return next; // 返回前缀函数数组
    }
}

2.3 KMP优化

• 这个方法需要对种字符串的next数组的特征要了解，毛毛张在下面举几个例子
  • 正例： 字符串abababab的next数组：[0, 0, 1, 2, 3, 4, 5, 6]
  • 正例： 字符串ababcababcababc的next数组：[0, 0, 1, 2, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
  • 反例： 字符串abcabca的next数组：[0, 0, 0, 1, 2, 3, 4]

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        int n = s.length(); // 获取字符串 s 的长度
        int[] next = getNext(s); // 生成字符串 s 的前缀函数数组
        int minLen = n - next[n - 1]; // 计算最小重复子串的长度
		//minLen < n 是为了防止这种情况:abcdef 此时minLen=0 
        // 如果最小长度小于字符串长度，并且字符串长度能够被最小长度整除，则存在重复子串
        if (minLen < n && n % minLen == 0) return true;
        
        return false; // 否则返回 false
    }

    // 生成前缀函数数组
    public int[] getNext(String s) {
        int n = s.length(); // 获取字符串 s 的长度
        int[] next = new int[n]; // 初始化前缀函数数组
        int j = 0; // 前缀指针
        next[0] = 0; // 第一个字符的前缀长度为 0

        // 遍历字符串，从第二个字符开始
        for (int i = 1; i < n; i++) {
            while (j > 0 && s.charAt(i) != s.charAt(j)) j = next[j - 1];// 当当前字符不匹配时，回退前缀指针 j
            if (s.charAt(i) == s.charAt(j)) j++;// 如果字符匹配，前缀长度增加
            next[i] = j;// 记录当前字符的前缀长度到 next 数组
        }
        
        return next; // 返回前缀函数数组
    }
}