【随想录】Day9—第四章 字符串part02

题目1: 459.重复的子字符串

• 题目链接：

1- 思路

移动匹配

• 判断字符串s是否由重复子串组成，只要两个s拼接在一起，里面还出现一个s的话，就说明是由重复子串组成。
• 当然，我们在判断 s + s 拼接的字符串里是否出现一个s的的时候，要刨除 s + s 的首字符和尾字符，这样避免在s+s中搜索出原来的s，我们要搜索的是中间拼接出来的s。

public class Solution {
    public boolean repeatedSubstringPattern(String s) {
        String t = s + s;
        t = t.substring(1, t.length() - 1); // 掐头去尾
        return t.contains(s); // 如果t中包含s，则返回true
    }
}

• contains 函数的时间复杂度为 O(n)

因此引入 kmp 判断一个字符串是否出现过另一个子串

KMP算法

• 前缀
  • 不包含尾字母，一定包含首字母的所有子串
• 后缀
  • 不包含首字母，一定包含为字母的所有子串

结论：如果字符串由重复子串构成，则其最小的重复子串，是它最长相等前后缀不包含的那一部分。

• 数组长度减去最长相同前后缀的长度相当于是第一个周期的长度，也就是一个周期的长度，如果这个周期可以被整除，就说明整个数组就是这个周期的循环。

1.Next数组的作用

• 遇见冲突，根据 next 数组做回退操作

2.Next数组的求解过程

• 初始化
• 处理前后缀不同的情况
• 处理前后缀相同的情况

最后更新 next 数组的值

• **此时需要两个指针 i 和 j：**其中 j 是指向前缀末尾位置，i 指向后缀末尾位置
• j = 0，next[0] = 0;
• i = 1 ; i<s.size();i++
• 前后缀不相等 回退
  • j>0 && s[i] != s[j] 发生不匹配
    - 回退 ：j = next[j-1]
  • s[i] == s[j] 前后缀相同
    • j++;
    • next[i] = j;

3.判断结果

• 如果len % (len - (next[len - 1] + 1)) == 0 ，则说明数组的长度正好可以被 (数组长度-最长相等前后缀的长度) 整除 ，说明该字符串有重复的子字符串。
• 数组长度减去最长相同前后缀的长度相当于是第一个周期的长度，也就是一个周期的长度，如果这个周期可以被整除，就说明整个数组就是这个周期的循环。

2- 题解

⭐重复的子字符串 ——题解思路

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;
        }
        return false;
    }
}

字符串总结

• 1. 反转字符串
• 2. 反转字符串II
• 3. 替换字符串中的数字
• 4. 反转字符串中的单词【5★】
• 5. 右旋转字符串【5★】

双指针总结

• 1. 数组
• 2. 链表
• 3. N数之和