最大重复子字符串【LC1668】
For a string sequence, a string word is k-repeating if word concatenated k times is a substring of sequence. The word’s maximum k-repeating value is the highest value k where word is k-repeating in sequence. If word is not a substring of sequence, word’s maximum k-repeating value is 0.
Given strings sequence and word, return the maximum k-repeating value of word in sequence.
给你一个字符串 sequence ，如果字符串 word 连续重复 k 次形成的字符串是 sequence 的一个子字符串，那么单词 word 的 重复值为 k 。单词 word 的 最****大重复值 是单词 word 在 sequence 中最大的重复值。如果 word 不是 sequence 的子串，那么重复值 k 为 0 。
给你一个字符串 sequence 和 word ，请你返回 最大重复值 k 。
双指针枚举所有起点
2022/11/3
- 思路：使用双指针定位sequence中的子字符串，如果sequence中的字符与word中的字符相同，那么后移快指针；如果不相同，那么更新最大重复子字符串的结果，并收缩慢指针，找到下一个起点
- 实现：
。对于一个子字符串的起点为slow、终点为fast，那么sequence[fast] 对应 word[(fast-slow) % word.length()]
。当sequence[fast] = word[(fast-slow) % word.length()]时，fast++
。当sequence[fast] != word[(fast-slow) % word.length()]时，最大重复值为(fast-slow) / word.length()
- 代码
class Solution { public int maxRepeating(String sequence, String word) { int slow = 0;// 子字符串的开头 int res = 0; int len = word.length(); while (slow < sequence.length() && sequence.charAt(slow) != word.charAt(0)){ slow++; } int fast = slow + 1;// 子字符串的末尾 while ( fast < sequence.length()){ if (sequence.charAt(fast) != word.charAt((fast-slow)%len) ){ res = Math.max(res,( fast - slow) / len); // 收缩慢指针 slow = slow + 1; while (slow < sequence.length() && sequence.charAt(slow) != word.charAt(0)){ slow++; } fast = slow + 1; }else{ fast++; } } if (slow < sequence.length()){ res = Math.max(res,(fast - slow) / len); } return res; } }
- 复杂度
。时间复杂度：O ( n m ),字符串sequence的长度为n,字符串word的长度为m
。空间复杂度：O ( 1 )
优化：找到下一个起点时使用KMP算法
KMP
class Solution { public int maxRepeating(String sequence, String word) { int n = sequence.length(), m = word.length(); if (n < m) { return 0; } int[] fail = new int[m]; Arrays.fill(fail, -1); for (int i = 1; i < m; ++i) { int j = fail[i - 1]; while (j != -1 && word.charAt(j + 1) != word.charAt(i)) { j = fail[j]; } if (word.charAt(j + 1) == word.charAt(i)) { fail[i] = j + 1; } } int[] f = new int[n]; int j = -1; for (int i = 0; i < n; ++i) { while (j != -1 && word.charAt(j + 1) != sequence.charAt(i)) { j = fail[j]; } if (word.charAt(j + 1) == sequence.charAt(i)) { ++j; if (j == m - 1) { f[i] = (i >= m ? f[i - m] : 0) + 1; j = fail[j]; } } } return Arrays.stream(f).max().getAsInt(); } } 作者：力扣官方题解 链接：https://leetcode.cn/problems/maximum-repeating-substring/solutions/1943410/zui-da-zhong-fu-zi-zi-fu-chuan-by-leetco-r4cp/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
- 复杂度
。时间复杂度：O ( n + m )，字符串sequence的长度为n,字符串word的长度为m
。空间复杂度：O ( n + m )
序列DP
sequence的长度为n，word的长度为m
1.确定dp数组（dp table）以及下标的含义
dp[i]:以sequence[i-1]结尾时最大的重复值
2.确定递推公式
截取子串sub = sequence.substring(i-m,i)
。如果sub = word
dp[i] = dp[i-m] +1 ;
3.如何初始化
。dp[0]=0;
4.确定遍历顺序
由dp公式可知，正序遍历i，从i=m开始遍历i
5.举例推导dp数组
- 代码
class Solution { public int maxRepeating(String sequence, String word) { int res = 0; int n = sequence.length(),m = word.length(); int[] dp = new int[n+1]; for (int i = m ; i <= n; i++){ String sub = sequence.substring(i-m,i); if (word.equals(sub)){ dp[i] = dp[i-m] + 1; res = Math.max(res,dp[i]); } } return res; } }
- 复杂度
。时间复杂度：O ( n ),字符串sequence的长度
。空间复杂度：O ( n )
