社区首页 >问答首页 >最长重复和不重叠子字符串

最长重复和不重叠子字符串
EN

Code Review用户
提问于 2016-10-03 17:08:41
回答 1查看 1.4K关注 0票数 3

给定一个字符串,在其中查找最长重复、不重叠子字符串的长度。换句话说,找到两个最大长度相同且不重叠的子字符串。

示例:

投入: str = "aabaabaaba“

产出: 4(aaba)

投入: str = "aaaaaaaaaaa“

产出: 5(aaaaa)

投入: str =“香蕉”

产出:2(a或na)

我编写了下面的递归代码。

代码语言:javascript
代码运行次数:0
复制
#include<bits/stdc++.h>
using namespace std;

void f(string str, int i, int j, int len,int& mx_len){
    mx_len = max(mx_len,len);       
    if(j>=str.length())
        return; 
    if(str[i]==str[j] && (j-i) > len)
        f(str,i+1,j+1,len+1,mx_len);    
    f(str,i+1,j+1,0,mx_len);    
    f(str,i,j+1,0,mx_len);
}

int main(){
    string s;
    cin>>s;
    int mx_len=0;   
    f(s,0,1,0,mx_len);  
    cout<<mx_len<<endl;
    return 0;
}

我理解这可以通过动态规划来完成。我在这里的重点是学习递归风格。

我正在编写3条导致递归调用的语句。是否可以减少导致递归调用的语句数?

除了使其成为动态编程(通过缓存或制表)之外,还可以在这段代码中进行哪些更改以使其更好呢?

同时,也要对编码风格进行评论。

EN

回答 1

Code Review用户

发布于 2016-10-03 20:03:22

编码风格可以使用一个良好的清理,使其不言自明。这将提高可读性,这将提高理解和分析。

首先,我会为每件事选择有意义的名字。"i“、"j”和"mx_len“应该更好地解释它们所代表的内容,如FirstSubstringPos等。"f”应该用它所做的重命名,例如"SearchForAShorterMatch()“下一步,我会将"f”包装在一个友好的初始化函数中,该函数只接受输入字符串,适当地设置其余的值,然后调用f函数。在命名其目的的bool返回函数中包装每个"if“子句,例如"IsSecondSubstringAsLongAsPossible()”。

更有用的名称将有助于调用和扩展代码以生成所需的输出。

一旦您的函数和变量有了解释名称,一些单元测试也将提高可用性,并有助于测试角落案例。

测试还可能有助于分析,以确定是否有一个地方可以将递归简化为更简单的函数调用(如果存在,则可能在处理第二个子字符串中)。

票数 0
EN
页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://codereview.stackexchange.com/questions/143157

复制
相关文章
LeetCode:最长不含重复字符的子字符串
  以abcabcbb为例,找出以每个字符结束,不包含重复字符的最长子串。那么其中最长的那个字符串即为答案。对于示例一中的字符串,我们列举出这些结果,其中括号中表示选中的字符以及最长的字符串:
Wu_Candy
2022/07/04
8690
LeetCode:最长不含重复字符的子字符串
LeetCode - #3 最长未重复子字符串
我们社区从本期开始会将顾毅(Netflix 增长黑客,《iOS 面试之道》作者,ACE 职业健身教练。微博:@故胤道长[1])的 Swift 算法题题解整理为文字版以方便大家学习与阅读。
Swift社区
2021/11/26
5020
LeetCode - #3 最长未重复子字符串
最长重复子数组
​ 模板题直接上dp,dp[i] [j] 为A数组以 i 结尾,B数组以 j 结尾的最长公共子串长度。
你的益达
2020/08/05
1.6K0
最长无重复子串
其次,在循环中,我们应能知道起始的位置,然后终止于哪个位置,当碰到终止的时候必然是元素为已经纳入我们统计中的元素。然后我们要如何确认这个元素在哪个位置,并且把一些废弃的元素丢弃掉,重新到下一次统计,直至目标数组遍历完全。
忧愁的chafry
2022/10/30
3040
最长无重复子串
求字符串内不包含重复字符的最长子串
        一个字符串,求这个字符串中不包含重复字符的最长子串的长度,如abba返回2,aaaaabc返回3,bbbbbbb返回1,等等上面是测试用例。那么我解决这个问题的思路有两种:
actionzhang
2022/11/30
1.1K0
【leetcode】最长不重复子串
这是一条在面试猿辅导一面时的题目,目前需要手写算法的公司不是很多,但小伙伴们也要未雨绸缪,包括一条也是,一直缺乏这方面的训练,话不多说,看题。
一条coding
2021/08/12
1.2K0
【leetcode】最长不重复子串
最长连续不重复子序列
给定一个长度为 n 的整数序列,请找出最长的不包含重复的数的连续区间,输出它的长度。
GeekLiHua
2025/01/21
440
动态规划:最长重复子数组
题目链接:https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/
代码随想录
2021/03/16
5790
动态规划:最长重复子数组
最长连续不重复子序列
Original Link 思想: 双指针。 快指针 i 作为某一连续最长不重复区间的右端点,慢指针 j 作为该区间的左端点; 遍历数组 a[i],用 vis[a[i]] 标记当前区间已经存在的数。 当 vis[a[i]] > 1 时: 说明当前区间存在重复数字,则 j 不断右移,期间 vis[a[j]] --,直到 vis[a[i]] == 1 为止; 此时不含重复数字的区间长度即为 i - j + 1,用 res 来维护最长的区间长度。 否则说明当前区间还未存在重复数字,i 持续右移。 代码: #i
浪漫主义狗
2023/02/16
2470
【简单】最长连续不重复子序列
给定一个长度为 n 的整数序列,请找出最长的不包含重复数字的连续子序列,输出它的长度。
字节星球Henry
2021/08/09
1.1K0
【剑指Offer】48. 最长不含重复字符的子字符串
输入一个字符串(只包含 a~z 的字符),求其最长不含重复字符的子字符串的长度。例如对于 arabcacfr,最长不含重复字符的子字符串为 acfr,长度为 4。
瑞新
2020/12/07
6920
DS串应用—最长重复子串
求串的最长重复子串长度(子串不重叠)。例如:abcaefabcabc的最长重复子串是串abca,长度为4。
叶茂林
2023/07/30
2830
剑指OfferV2(增) -- 最长不含重复字符的子字符串
这道题,可以使用哈希表解决,使用哈希表主要是为了保存字符最后一次出现的索引位置,同时记录开始索引位置start和最长的不包含 重复字符的子字符串长度len;
秦怀杂货店
2022/02/15
3660
获取两个字符串的最长重复子串
doc2
2024/08/29
720
LeetCode 718. 最长重复子数组(DP)
1. 题目 给两个整数数组 A 和 B ,返回两个数组中公共的、长度最长的子数组的长度。 示例 1: 输入: A: [1,2,3,2,1] B: [3,2,1,4,7] 输出: 3 解释: 长度最长的公共子数组是 [3, 2, 1]。 说明: 1 <= len(A), len(B) <= 1000 0 <= A[i], B[i] < 100 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/maximum-length-of-repeated-su
Michael阿明
2020/07/13
5640
图解LeetCode——剑指 Offer 48. 最长不含重复字符的子字符串
根据题目描述,我们要确保找到的子字符串中不包含重复字符。那么我们创建一个head指针,用于指向子字符串中的第一个字符。
爪哇缪斯
2023/05/10
2340
图解LeetCode——剑指 Offer 48. 最长不含重复字符的子字符串
LeetCode-面试题48-最长不含重复字符的子字符串
第一二种情况可以合并为一个,由于返回值取dp列表最大值,可以借助dp变量,存储dp[j],每轮更新res
benym
2022/07/14
2810
重复字符串 leetcode_求字符串的最长无重复字符串
0 <= s.length <= 5 * 104 s 由英文字母、数字、符号和空格组成
全栈程序员站长
2022/09/22
8520
最长不重复子串的有趣解法
最长不重复子串是leetcode一道经典的题目,要求找出一个字符串中最长不重复子串的长度
泽霖
2023/11/29
1690
【字符串】最长公共前缀 && 最长回文子串
​ 这道题模拟的思路有两种,第一种就是每次比较每个字符串同一位置的字符,判断是否相等,如果不相等则返回前面匹配的位置,可以使用 substr() 函数直接实现这块!
利刃大大
2025/02/27
480

相似问题

LeetCode 1044:最长重复子字符串

10

最长的子字符串,不重复字符,Haskell

10

优化代码:最长的重复子字符串

20

Leetcode:最长的子字符串,不重复字符

10

在字符串中查找最长的重复子字符串

10
添加站长 进交流群

领取专属 10元无门槛券

AI混元助手 在线答疑

扫码加入开发者社群
关注 腾讯云开发者公众号

洞察 腾讯核心技术

剖析业界实践案例

扫码关注腾讯云开发者公众号
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
查看详情【社区公告】 技术创作特训营有奖征文