题目分析

因为本题的数据范围很小，所以这个题目是一个简单题，但是蕴含的优化方法非常多，小伙伴们看一下会写哪几种呢？

动态规划

动态规划方法容易想到，设dp[i]表示以第i个字符结尾能匹配的最大重复值k。可推出状态转移方程

$$ dp[i] = \begin{cases} dp[i - wn] + 1 & s.substring(i - wn, i) == w \\ 0 & else \end{cases} $$

上式中wn为word的长度

算法的时间复杂度为O(mn)，空间复杂度为O(n)。

class Solution {
    public int maxRepeating(String sequence, String word) {
        int sn = sequence.length();
        int wn = word.length();
        int[] dp = new int[sn + 1];
        for (int i = wn; i <= sn; i++) {
            if (sequence.substring(i - wn, i).equals(word)) {
                dp[i] = dp[i - wn] + 1;
            }
        }
        return Arrays.stream(dp).max().getAsInt();
    }
}

二分查找

二分查找也是比较容易想到的，一般求最大值或者最小值，都可以考虑是否能用二分查找。

本题k的最小值为0，最大值为sn / wn，因此可以二分k的值，然后索引该字符串。

算法的时间复杂度为O(nlog(n))，空间复杂度为O(n)。

class Solution {
    public int maxRepeating(String sequence, String word) {
        int sn = sequence.length();
        int wn = word.length();
        int left = 0;
        int right = sn / wn;
        while (left < right) {
            int mid = (left + right + 1) >> 1;
            if (sequence.indexOf(getString(word, mid)) != -1) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
    
    private String getString(String word, int n) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(word);
        }
        return sb.toString();
    }
}

KMP算法

KMP算法可以参考KMP算法，里面有详细的思路和证明

本题使用这种做法比KMP算法困难一些，要结合动态规划的思想，因为使用KMP匹配了一个word后，可能还需要匹配另一个。

因此当j == wn时，和第一种动态规划方法相同，dp[i] = dp[i - wn] + 1，但是j也要回退到next[j]，因为next数组长度是wn的，因此next[j] = next[wn]会数组越界，所以在getNext时，要创建长度为wn + 1的数组。

算法的时间复杂度为O(n)，空间复杂度为O(n)。

class Solution {
    private int sn;

    private int wn;

    public int maxRepeating(String sequence, String word) {
        sn = sequence.length();
        wn = word.length();
        int[] next = getNext(word);
        int i = 0;
        int j = 0;
        int[] dp = new int[sn + 1];
        while (i < sn && j < wn) {
            if (j == -1 || sequence.charAt(i) == word.charAt(j)) {
                i++;
                j++;
                if (j == wn) {
                    dp[i] = dp[i - wn] + 1;
                    j = next[j];
                }
            } else {
                j = next[j];
            }
        }
        return Arrays.stream(dp).max().getAsInt();
    }

    private int[] getNext(String word) {
        int[] next = new int[wn + 1];
        Arrays.fill(next, -1);
        int i = 0;
        int j = -1;
        while (i < wn) {
            if (j == -1 || word.charAt(i) == word.charAt(j)) {
                next[++i] = ++j;
            } else {
                j = next[j];
            }
        }
        return next;
    }
}

字符串哈希算法

字符串哈希可以参考字符串哈希，里面有详细的思路和证明

字符串哈希和KMP算法都可以看成是DP的优化方案，只不过将字符串匹配的方式进行了优化

这里直接看代码即可。

class Solution {
    public int maxRepeating(String sequence, String word) {
        int sn = sequence.length();
        int wn = word.length();
        int base = 1;
        int factor = 27;
        int hashcode = 0;
        int[] curSum = new int[sn + 1];
        for (int i = 1; i <= sn; i++) {
            curSum[i] = curSum[i - 1] * factor + sequence.charAt(i - 1) - 'a';
        }
        for (int i = 0; i < wn; i++) {
            base *= factor;
            hashcode = hashcode * factor + word.charAt(i) - 'a';
        }
        int[] dp = new int[sn + 1];
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i <= sn - wn; i++) {
            int j = i + wn;
            int cur = curSum[j] - curSum[i] * base;
            map.put(j, cur);
            if (cur == hashcode) {
                dp[j] = dp[i] + 1;
            }
        }
        return Arrays.stream(dp).max().getAsInt();
    }
}

刷题总结

本题可以稍微增加一些数据量，变成一个mid的难度。本题最基础的方法是前两个，尤其是二分，一定要能够熟练掌握。对于后面两种特定算法，希望小伙伴们可以多学习一些，以备不时之需。