Skip to main content
added 1927 characters in body
Source Link
Zeta
  • 19.6k
  • 2
  • 57
  • 90

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);
        }
    }
}

Further remarks

Further remarks

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);
        }
    }
}

Further remarks

Source Link
Zeta
  • 19.6k
  • 2
  • 57
  • 90

Includes and namespaces

First of all, bits/stdc++.h isn't part of the C++ standard. Instead, only include the files you actually need:

#include <iostream>
#include <string>

Next, it's considered bad practice to use using namespace …, so let's get rid of it.

Your function f

There are several things we can improve here. First of all, it's name is ambiguous. What does f do? It calculates the length of the longest repeating and non-overlapping substring. Let's give it a better name and type:

size_t longest_repeating_substring_length(const std::string & str){
    …
}

'But wait', I here you say. 'That's not my function anymore'. It sure isn't. The problem with your function is that it's possible to use it wrong, e.g.

f("123", 100, 0, 0,mx_len);
//       ^^^ oh oh

It's a fine way to implement the dynamic approach, but it shouldn't be available to the user by default. Therefore, let's "hide" it:

namespace detail {
    void longest_repeating_substring_length(
        const std::string & str, size_t i, size_t j, size_t len, size_t & mx_len
    ){
        mx_len = std::max(mx_len,len);

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

Why is the const std::string& necessary? First of all, const will make sure that we don't accidentially change your string in our function. And & will get rid of additional copies that would happen throughout the execution.

Note that we can get rid of mx_len:

namespace detail {
    size_t longest_repeating_substring_length(
        const std::string & str, size_t i, size_t j, size_t len
    ){
        size_t mx_len = len;

        if(j >= str.length()) {
            return mx_len; 
        }
        if(str[i] == str[j] && (j - i) > len) {
            mx_len = longest_repeating_substring_length(str,i+1,j+1,len+1);    
        }
        mx_len = std::max(mx_len, longest_repeating_substring_length(str,i+1,j+1,0));    
        mx_len = std::max(mx_len, longest_repeating_substring_length(str,i,j+1,0);
        return mx_len;
    }
}

Depending on which variant you'll use, you end up with the following code:

namespace detail {
    void longest_repeating_substring_length(
        const std::string & str, size_t i, size_t j, size_t len, size_t & mx_len
    ){
        mx_len = std::max(mx_len,len);

        if(j >= str.length()) {
            return; 
        }
        if(str[i] == str[j] && (j - i) > len) {
            longest_repeating_substring_length(str,i+1,j+1,len+1,mx_len);    
        }

        longest_repeating_substring_length(str,i+1,j+1,0,mx_len);    
        longest_repeating_substring_length(str,i,j+1,0,mx_len);
    }
}

size_t longest_repeating_substring_length(const std::string & str){
    size_t max_length = 0;
    detail::longest_repeating_substring_length(str, 0, 1, 0, max_length);

    return max_length;
}

Easy-to-use function at global namespace, and function that can possibly get used in a wrong way hidden away in detail.

Which brings us to your new main:

int main(){
    std::string s;
    std::cin >> s;

    std::cout<< longest_repeating_substring_length(s) <<std::endl;

    return 0;
}

Further remarks

Your code could get a lot more readable if you used more whitespace. Also, for difficult functions, you really want to add comments and/or documentation.