最长重复和不重叠子字符串
给定一个字符串，在其中查找最长重复、不重叠子字符串的长度。换句话说，找到两个最大长度相同且不重叠的子字符串。
示例：
投入: str = "aabaabaaba“
产出: 4(aaba)
投入: str = "aaaaaaaaaaa“
产出: 5(aaaaa)
投入: str =“香蕉”
产出:2(a或na)
我编写了下面的递归代码。
#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条导致递归调用的语句。是否可以减少导致递归调用的语句数？
除了使其成为动态编程(通过缓存或制表)之外，还可以在这段代码中进行哪些更改以使其更好呢？
同时，也要对编码风格进行评论。
回答 1
Code Review用户
发布于 2016-10-04 04:03:22
编码风格可以使用一个良好的清理，使其不言自明。这将提高可读性，这将提高理解和分析。
首先，我会为每件事选择有意义的名字。"i“、"j”和"mx_len“应该更好地解释它们所代表的内容，如FirstSubstringPos等。"f”应该用它所做的重命名，例如"SearchForAShorterMatch()“下一步，我会将"f”包装在一个友好的初始化函数中，该函数只接受输入字符串，适当地设置其余的值，然后调用f函数。在命名其目的的bool返回函数中包装每个"if“子句，例如"IsSecondSubstringAsLongAsPossible()”。
更有用的名称将有助于调用和扩展代码以生成所需的输出。
一旦您的函数和变量有了解释名称，一些单元测试也将提高可用性，并有助于测试角落案例。
测试还可能有助于分析，以确定是否有一个地方可以将递归简化为更简单的函数调用(如果存在，则可能在处理第二个子字符串中)。
https://codereview.stackexchange.com/questions/143157
复制相似问题
腾讯云开发者
