题目
给你一个字符串 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" 的子字符串。
解题
方法一：字典树
class Trie{ public: vector<Trie*> next; bool isEnd; Trie(){ next=vector<Trie*>(26,nullptr); isEnd=false; } void insert(string&& word){ Trie* node=this; for(char c:word){ if(node->next[c-'a']==nullptr){ node->next[c-'a']=new Trie(); } node=node->next[c-'a']; } node->isEnd=true; } }; class Solution { public: int maxRepeating(string sequence, string word) { int res=0; Trie* trie=new Trie(); int n=sequence.size(); //把所有情况都放入字典树查找 for(int i=0;i<n;i++){ trie->insert(sequence.substr(i,n-i)); } //查看重复出现了几次 Trie* node=trie; while(true){ for(char c:word){ if(node->next[c-'a']) node=node->next[c-'a']; else return res; } res++; } return res; } };
方法二：序列DP
dp[i]表示以 sequence索引i-1为结尾时的最大重复次数
class Solution { public: int maxRepeating(string sequence, string word) { int n=sequence.size(),m=word.size(); vector<int> dp(n+1,0); int res=0; for(int i=1;i<=n;i++){ if(i>=m&&sequence.substr(i-m,m)==word) dp[i]=max(dp[i],dp[i-m]+1); res=max(res,dp[i]); } return res; } };
