首页 > 代码库 > 459.(KMP)求字符串是否由模式重复构成 Repeated Substring Pattern
459.(KMP)求字符串是否由模式重复构成 Repeated Substring Pattern
假设str长度为len,重复的子串长度为k,则如果真的由连续多个长度为k的子串重复构成str,那么在对str求next时,由于连续对称性(如图,前后两个虚线框内字符串相等),会从next[k+1]开始,1,2,3...地递增,直到next[len]=len-k,且(len-k)%k==0,表示有整数个k
要一直求到next[len]而不是next[len-1],是因为next[len-1]只是表示前len-1个字母的内部对称性,而没有考虑到最后一个字母即str[len-1]
所以求解很简单:先对str求next数组,一直求到next[len],然后看看next[len]是否非零且整除k(k=len-next[len])
public class Solution {
public bool RepeatedSubstringPattern(string str) {
int length = str.Length;
int[] next = new int[length+1];//length+1 求最大公共元素长度数组
next[0] = -1;
int j = 0;
int k = -1;
while (j < length) {
if (k == -1 || str[j] == str[k]) {
++j;
++k;
next[j] = k;
} else {
k = next[k];
}
}
return next[length] != 0 && next[length] % (length - next[length]) == 0;
}
}
来自为知笔记(Wiz)
459.(KMP)求字符串是否由模式重复构成 Repeated Substring Pattern
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。