• LeetCode每日一题:1668. 最大重复子字符串 (简单) 字符串查找/枚举/kmp+dp/序列dp


    题目:1668. 最大重复子字符串

    给你一个字符串 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. class Solution {
    3. public:
    4. int maxRepeating(string sequence, string word) {
    5. //string.find()函数,查找子串,找到则返回子串起始下标,找不到返回-1或string::npos
    6. if( sequence.find(word) == -1 ) return 0;
    7. string s = word + word;
    8. int ans = 1 ;
    9. while( sequence.find(s) != string::npos){
    10. ans++ ;
    11. s += word;
    12. }
    13. return ans ;
    14. }
    15. };

    序列dp 

    1. class Solution {
    2. public:
    3. int maxRepeating(string sequence, string word) {
    4. int n = sequence.size() , m = word.size() ;
    5. int ans = 0 ;
    6. vector<int> f(n+10,0);
    7. for(int i = m ; i <= n ; i++ ){
    8. if(sequence.substr(i-m,m)==word)
    9. f[i] = f[i-m] + 1;
    10. ans = max( ans , f[i]);
    11. }
    12. return ans ;
    13. }
    14. };
  • 相关阅读:
    如何预防最新的Mallox变种malloxx勒索病毒感染您的计算机?
    Maven的使用
    Docker基础
    python-wordcloud词云
    【算法】分治法的应用——快速排序
    嵌入式Linux应用开发-Framebuffer 应用编程
    Linux下如何操作寄存器
    FFMPEG 推流至 NGINX-RTMP 服务
    一套基于tailwindcss的后台管理系统模板Chakra UI + React + TS
    GoWeb——Gin框架入门(第一章)
  • 原文地址:https://blog.csdn.net/weixin_53439401/article/details/127662169