leetcode-动态规划

1668. 最大重复子字符串
输入：sequence = "ababc", word = "ab"
输出：2
解释："abab" 是 "ababc" 的子字符串。

class Solution {
public:
    int maxRepeating(string sequence, string word) {
        int n= sequence.size();
        vector<int> dp(n+1);
        int k = word.size();
        for (int i=k;i< n + 1;i++){
            if ( sequence.substr(i-k,k)==word ) {
                dp[i]=dp[i-k] +1;
            }   
        }
        sort(dp.begin(), dp.end());
        return dp[n];
    }
};

python

class Solution:
    def maxRepeating(self, sequence: str, word: str) -> int:
        dp=[0]*(len(sequence)+1)
        k=len(word)
        for i in range(k,len(sequence)+1):
            if sequence[i-k:i]==word:
                dp[i]=dp[i-k]+1
        return max(dp)