首页 > 代码库 > 459.（KMP）求字符串是否由模式重复构成 Repeated Substring Pattern

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

2024-08-31 14:20:20   222人阅读


假设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


联系
我们