首页 > 代码库 > 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])



  1. public class Solution {
  2. public bool RepeatedSubstringPattern(string str) {
  3. int length = str.Length;
  4. int[] next = new int[length+1];//length+1 求最大公共元素长度数组
  5. next[0] = -1;
  6. int j = 0;
  7. int k = -1;
  8. while (j < length) {
  9. if (k == -1 || str[j] == str[k]) {
  10. ++j;
  11. ++k;
  12. next[j] = k;
  13. } else {
  14. k = next[k];
  15. }
  16. }
  17. return next[length] != 0 && next[length] % (length - next[length]) == 0;
  18. }
  19. }



来自为知笔记(Wiz)


459.(KMP)求字符串是否由模式重复构成 Repeated Substring Pattern