算法力扣刷题 二十六【459.重复的子字符串】

前言

字符串篇，继续。
记录 二十六【459.重复的子字符串】

---

一、题目阅读

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

示例 1:

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

示例 2:

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

示例 3:

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

提示：

1 <= s.length <= 104
s 由小写英文字母组成

---

二、尝试实现

思路

上一篇学到匹配字符串可以用KMP算法，用来查找“文本串”中有没有“模式串”。用到前缀表。
乍一看题目，觉得也是匹配的问题，所以用前缀表试一下。
（1）对string s求出next数组。（数组保持原始数值，next[0] == 0）
（2）如果能知道从哪里开始重复就好了，在此之前的长度是x，是最小的重复单元。用size%x ==0，说明满足条件，return true。否则return false。
（3）怎么找规律，找最小重复单元？

• next某个位置等于1，后面的值都递增。发现开始重复的位置next值为1，往后2,3,4……，找next中哪个位置等于0？倒着往前找哪个next等于1？倒着往前找递减，并且终止在1,？这都不全面，有些用例无法通过，实现不了。

所以：获得next数组之后怎么确定最小重复单元呢？这是个关键。

---

三、代码随想录学习

学习内容

继续二、中的思路，获取到next数组后，学习到：

• 只需要看next[size-1]，最后一位的数值。最长相等前后缀的含义，给出了最小重复单元。
• 图示讲解推理过程。
  
• size - next[size-1] ：最小重复单元的长度，如果size可以除尽，说明返回true；否则返回false。
• next[size-1] != 0再做减法。

代码实现

class Solution {
public://求前缀表void getNext(int* next,string& s){next[0] = 0;int j=0;for(int i = 1;i < s.size();i++){while(j >0 && s[j] != s[i]){j = next[j-1];}if(s[j] == s[i]){j++;}next[i] = j;}return;}bool repeatedSubstringPattern(string s) {int size = s.size();int* next = new int[size]{0};getNext(next,s);if(next[size-1] != 0 &&size%(size-next[size-1]) == 0){	//在next[size-1]!= 0前提下，确定最小重复单元的长度，判断是否整除return true;}else{return false;}}
};

---

总结

KMP用前缀表找匹配很有用。利用前缀 = 后缀，并且最长的“含义”来找所求。

（欢迎指正，转载标明出处）