(第15天)【leetcode题解】459、重复的子字符串

459、重复的子字符串

题目描述

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

暴力匹配

思路

1. 推理

• 如果存在这样的子串，那么这个子串一定是s的前缀。
• s的长度n一定是子串长度n1的整数倍
• s中的元素s[i]与往前移n1的元素s[i-n1]相同

2. 方法

因此从小到大枚举出所有可能的子串长度n1，再对这个子串进行上述的判断即可。
优化：这个子串至少要在s中重复一次，所以n1的范围为[1,n/2]。

代码

class Solution {
public:bool repeatedSubstringPattern(string s) {int n = s.size();//i代表子串的长度，应从1开始for (int i = 1; i <= n / 2; i++) {//判断该子串是否为目标子串if (n % i == 0) {bool match = true;//判断之后的字符往前移子串长度i之后是否相等//从子串之后开始遍历整个字符串for (int j = i; j < n; j++) {if (s[j] != s[j - i]) {match = false;break;} }if (match) return true;}}return false;}
};

时间复杂度：O(n²)；枚举子串的时间复杂度为O(n)，遍历判断子串的时间复杂度为O(n)。
空间复杂度：O(1)；

字符串匹配

思路

1. 如果s满足题目要求，那么s具有以下性质：

• 设s的长度为n，子串长度s1为n1.
• 可以把s写成n/n1个子串s1排列的形式 ： s——>s1s1s1s1…
• 那么把第一个s1移到最后面，字符串s不变

2. 根据性质，可以证明：

• 因为1 <= n1 < n，那么把两个字符串s连在一起得到S
• 把连在一起后的字符串S移除前后第一个元素
• 这时，字符串s一定是拼接串S的子串

3. 根据证明结果，得到方法：

• 拼接两个字符串s
• 移除第一个和最后一个字符
• 如果s是其中的子串，则满足题目要求

代码

class Solution {
public:bool repeatedSubstringPattern(string s) {return (s + s).find(s, 1) != s.size();}
};

与暴力匹配的不同

通过推理，得到一种满足要求是的情况，只要针对这个情况进行判断即可。

KMP解法

思路

1. 假设推理

• 假设这个文本串由重复子串组成
• 找到这个文本串的最长公共前后缀
• 文本串切割掉最长公共前后缀，剩下的就是重复子串

2. 可用的结论

• 设文本串s由n个长度为x的子串组成，则文本串全长为nx。
• 最长公共前后缀由m个长度为x的子串组成，长度为mx。
• 则重复子串长度为(n-m)x。n-m=1
• 当全长nx对重复子串长度(n-m)x取余等于0时(即nx % (n-m)x == 0 or nx % x == 0)，证明(n-m)x代表的子串为重复子字符串。

3. 方法

• 求出next数组，next数组长度为len
• 使用next数组存储文本串中最长公共前后缀的长度next[len - 1]
• 如果 len % (len -next[len - 1]) == 0，则表明存在重复子字符串

代码

class Solution {
public://得出next数组void getNext(int* next, string& s) {//初始化int j = 0;//前缀末尾从0开始next[0] = j;//从长度为2的子串开始求最长公共前后缀长度for (int i = 1; i < s.size(); i++) {//前后缀末尾不匹配时while (j >0 && s[i] != s[j]) j = next[j - 1];//j回退//前后缀末尾匹配时if (s[i] == s[j]) {j++;//j(和i)往后移一位}next[i] = j;//下标j为当前子串(末尾下标为i)的最长公共前后缀长度}}bool repeatedSubstringPattern(string s) {int next[s.size()];//创建长度为字符串长度的前缀表getNext(&next[0], s);//使用最长公共前后缀长度判断是否由重复的子字符串组成int len = s.size();//next[len - 1] == 0时，证明整个字符串最长公共前后缀长度为0//根据推理得出的结论:当len % (len - next[len-1]) == 0 时证明(有重复的子字符串/最后一段字符串为重复子字符串)if (next[len - 1] != 0 && len % (len - next[len-1]) == 0) return true;return false;}
};

时间复杂度：O(n)；得到前缀表时遍历字符串需要O(n)，判断重复子字符串只用了固定的操作数。
空间复杂度：O(n)；需要前缀表存储字符串的所有前缀子串(包括它自身)的最长公共前后缀长度。

KMP算法的核心和用途

1. 核心

• 前缀表next，其中存储了字符串的最长公共前后缀长度。
• 匹配时，使用前缀表记录的最长公共前后缀长度来进行回退。
• 总结：存储字符串的最长公共前后缀长度的前缀表、回退思想。

2. 用途

• 使用前缀表回退查找子字符串。
• 使用前缀表中记录的最长公共前后缀长度来进行一些数字上的判断。