Less recursive calls
To get the number of recursive calls down, we have to ask ourselfs "how large can mx_len get in that particular call?"
Well, if we start at position I and J, the maximum we can get is limited by J-I (since we may not overlap both strings) and str.length() - J (since there are only so many characters starting from the second position.
So let's calculate the maximum length we could get for a string:
#include <cassert>
size_t max_length(size_t string_length, size_t first_pos, size_t second_pos) {
assert(first_pos <= second_pos);
assert(second_pos <= string_length);
return std::min(second_pos - first_pos, string_length - second_pos);
}
size_t max_length(const std::string &s, size_t first_pos, size_t second_pos) {
return max_length(s.size(), first_pos, second_pos);
}
Now we have a method to determine in \$\mathcal O(1)\$ whether we should continue a recursive call:
namespace detail {
void longest_repeating_substring_length(
const std::string & str, size_t i, size_t j, size_t len, size_t & mx_len
){
// i is always less than j, otherwise we broke our algorithm
assert(i <= j);
// the current max
mx_len = std::max(mx_len,len);
if(j >= str.length()) {
return;
}
if(str[i] == str[j] && (j - i) > len && max_length(str,i,j) <= mx_len) {
longest_repeating_substring_length(str,i+1,j+1,len+1,mx_len);
}
if(max_length(str, i + 1, j + 1) > mx_len){
longest_repeating_substring_length(str,i+1,j+1,0,mx_len);
}
if(max_length(str, i, j + 1) > mx_len){
longest_repeating_substring_length(str,i,j+1,0,mx_len);
}
}
}