qidao123.com技术社区-IT企服评测·应用市场
标题:
leetcode459 重复的子字符串 周期性字符串问题 KMP算法
[打印本页]
作者:
缠丝猫
时间:
7 天前
标题:
leetcode459 重复的子字符串 周期性字符串问题 KMP算法
1.移动匹配法：
如果一个字符串s是周期串，则s+s的中间肯定有一部分s
我们在判定 s + s 拼接的字符串里是否出现一个s的的时间，
要刨除 s + s 的首字符和尾字符
，这样避免在s+s中搜索出原来的s，我们要搜索的是中间拼接出来的s。
begin()返回向量头指针，指向第一个元素
end()返回向量尾指针，指向向量最后一个元素的下一个位置
t.find(s) 是 std::string 的成员函数，用于在字符串 t 中查找子串 s
std::string::npos 是一个常量，表示“未找到”或“无效位置”
class Solution {
public:
bool repeatedSubstringPattern(string s) {
string t = s + s;
t.erase(t.begin());
t.erase(t.end()-1);
if(t.find(s) != string::npos) return true;
return false;
}
};
复制代码
2.KMP法：最小重复单元就是最长相等前后缀不包罗的那个部分
公式：len(s) % (len(s) - maxLen) = 0
此中
len(s) 为字符串 s 的长度
，
maxLen 为最长公共前后缀的长度
。
如果 s 是周期串，那【s 的长度】是【s 的长度减去最长公共前后缀的长度】的倍数，那字符串 s 就是周期串
。
如果是周期串，那对应位置上的字母应该是一样的，如果对应位置上的字母不一样，那就肯定不是周期串
。maxLen == 0 or s[n - 1] != s[n - 1 - maxLen]
next数组存放的元素是某个阶段上重复的元素个数，由于能组成重复元素的长串next数组肯定是整体向上递增的（即使中间数字会有颠簸起伏），取next最后一个元素就是最长相同前后缀（即重复的元素个数，记为max），len - max就是最小重复子串长度，如果len能被最小重复字串长度整除，说明长串均可由其构成。
class Solution {
public:
void getNext(int* next, string s){
int i = 1;
int j = 0;
for(;i<s.size();i++){
while(j > 0 && s[j] != s[i]){
j = next[j-1];
}
if(s[j]==s[i]){
j++;
}
next[i] = j;
}
}
bool repeatedSubstringPattern(string s) {
if(s.size() == 0) return false;
vector<int> next(s.size());
getNext(&next[0], s);
int len = s.size();
if(next[len - 1] != 0 && len % (len - (next[len - 1])) == 0) {
return true;
}
return false;
}
};
复制代码
int next[s.size()];
这种定义方式在 C++ 中是
变长数组（VLA）
，虽然在某些编译器中支持，但并不是 C++ 标准的一部分。如果 s.size() 为 0，或者 next 数组的巨细不敷以容纳 s.size() 个元素，就会导致未定义行为。
需要修改。
if(next[len - 1] != 0 && len % (len - (next[len - 1])) == 0) {
return true;
}
return false;
你提到的例子 s = "abcabcd" 非常好！它确实是一个特别情况，可以资助我们更深入地明白 next 数组和最长公共前后缀的关系。
1.
分析 s = "abcabcd"
字符串 s = "abcabcd"，长度为 7。
我们手动计算它的 next 数组：
索引 (i)前缀 s[0..i]最长公共前后缀长度 (next
)0"a"01"ab"02"abc"03"abca"14"abcab"25"abcabc"36"abcabcd"0
next 数组为 [0, 0, 0, 1, 2, 3, 0]。
next[len - 1] = next[6] = 0。
2.
最长公共前后缀长度
对于 s = "abcabcd"，next[len - 1] = 0，表示整个字符串没有非平常的最长公共前后缀。
也就是说，字符串 s 的最长公共前后缀长度为 0。
3.
为什么 next[len - 1] 是最长公共前后缀长度？
next[len - 1] 表示前缀 s[0..len-1]（即整个字符串 s）的最长公共前后缀的长度。
如果 next[len - 1] = 0，说明整个字符串没有非平常的最长公共前后缀。
4.
特别情况分析
对于 s = "abcabcd"：
next[len - 1] = 0，表示整个字符串没有非平常的最长公共前后缀。
因此，字符串 s 不能由某个子串重复多次构成。
所以判定条件前面也加了next[len-1] != 0
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
欢迎光临 qidao123.com技术社区-IT企服评测·应用市场 (https://dis.qidao123.com/)
Powered by Discuz! X3.4