最大重复子字符串

给你一个字符串 sequence ，如果字符串 word 连续重复 k 次形成的字符串是 sequence 的一个子字符串，那么单词 word 的 重复值为 k 。单词 word 的 最大重复值 是单词 word 在 sequence 中最大的重复值。如果 word 不是 sequence 的子串，那么重复值 k 为 0 。给你一个字符串 sequence 和 word ，请你返回 最大重复值 k 。

示例 1：

输入：sequence = "ababc", word = "ab"
输出：2
解释："abab" 是 "ababc" 的子字符串。
示例 2：

输入：sequence = "ababc", word = "ba"
输出：1
解释："ba" 是 "ababc" 的子字符串，但 "baba" 不是 "ababc" 的子字符串。
示例 3：

输入：sequence = "ababc", word = "ac"
输出：0
解释："ac" 不是 "ababc" 的子字符串。
 

提示：

1 <= sequence.length <= 100
1 <= word.length <= 100
sequence 和 word 都只包含小写英文字母。

左右遍历

1. 从左往右计算连续重复的字符串的数量
2. 从右往左计算连续重复的字符串的数量
3. 计算最大值

   class Solution {
       public int maxRepeating(String sequence, String word) {
           char[] sq = sequence.toCharArray();
           int n = sequence.length();
           int len = word.length();
           int res = 0;
   
           int max = 0;
           boolean lastFlag = false;
           // 从左往右统计重复的word的数量
           for (int i = 0; i < sq.length; i++) {
               int c = 0;
               int index = i;
               // 从前往后判断是否与word相同
               for (int j = 0; j < word.length(); j++) {
                   index = i + j;
                   if (index < n && word.charAt(j) == sq[index]) c++;
                   else break;
               }
               i = index;
   
               if (c == len) {
                   lastFlag = true;
                   res++;
                   max = Math.max(max, res);
               } else {
                   lastFlag = false;
                   max = Math.max(res, max);
                   res = 0;
               }
           }
   
           lastFlag = false;
           res = 0;
           // 从右往左统计word的数量
           for (int i = sq.length - 1; i >= 0; i--) {
               int c = 0;
               boolean flag = false;
               // 从后往前判断是否与word相同
               for (int j = word.length() - 1; j >= 0; j--) {
                   if (i > -1 && word.charAt(j) == sq[i]) {
                       i--;
                       c++;
                       flag = true;
                   } else break;
               }
               // 上面多减了1，再加回来
               if (flag) i++;
               if (c == len) {
                   lastFlag = true;
                   res++;
                   max = Math.max(max, res);
               } else {
                   lastFlag = false;
                   max = Math.max(res, max);
                   res = 0;
               }
           }
           return max;
       }
   }

反向思考（从复制word入手）

复制word，判断sequence中是否包含word的复制字符串

class Solution {
    public int maxRepeating(String sequence, String word) {
        int count = 0;
        StringBuilder sb = new StringBuilder(word);
        while(sequence.contains(sb)) {
            count++;
            sb.append(word);
        }
        return count;
    }
}

作者：bobby996
链接：https://leetcode-cn.com/problems/maximum-repeating-substring/solution/1688ti-9249-4667-by-bobby996-nly6/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

赏

谢谢你请我吃糖果

微信