【Leetcode】466. 统计重复个数

题目

466. 统计重复个数

思路

题目要求找出一个最大整数 m，使得经过 n2 个字符串 s2 组成的字符串能够被经过 n1 个字符串 s1 组成的字符串完全包含的次数。使用动态规划来记录每个位置匹配的情况，并通过循环节的分析来计算最终的匹配次数。

代码

class Solution {
public:
    int getMaxRepetitions(string s1, int n1, string s2, int n2) {
        int len1 = s1.length();
        int len2 = s2.length();
        vector<vector<int>> next(len1 + 1, vector<int>(26, 0));
        vector<vector<int>> dp(len1 + 1, vector<int>(2, 0));

        for (int i = 0; i < 26; i++) {
            next[len1][i] = INT_MAX;
        }

        for (int i = len1 - 1; i >= 0; i--) {
            int idx = s1[i] - 'a';
            for (int j = 0; j < 26; j++) {
                next[i][j] = next[i + 1][j];
                if (j == idx) {
                    next[i][j] = i + 1;
                }
            }
        }

        for (int i = 0; i < len1 + 1; i++) {
            int count = 0;
            int offset = i;

            int j = 0;
            while (j < len2) {
                int idx = s2[j] - 'a';
                int pos = next[offset][idx];

                if (offset == 0 && pos == INT_MAX) {
                    return 0;
                }
                if (pos == INT_MAX) {
                    offset = 0;
                    count++;
                } else {
                    offset = pos;
                    j++;
                }
            }
            dp[i][0] = count;
            dp[i][1] = offset;
        }

        int p = 1;
        int total = 0;
        int offset = 0;
        while (p <= n1) {
            int count = dp[offset][0];
            int idx = dp[offset][1];
            if (p + count > n1) {
                break;
            }

            p = p + count;
            total++;
            offset = idx;
        }

        return total / n2;
    }
};