Longest Repeating Subsequence

lrs.cpp

// geeksforgeeks
// Longest Repeating Subsequence

#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    string input;
    cin >> input;
    vector<vector<int>> dp(input.size() + 1, vector<int>(input.size() + 1, 0));
    // basically finding the longest common substring of input and itself
    // with a constraint that character in same position of input is not allowed
    for (size_t i = 1; i <= input.size(); i++)
        for (size_t j = 1; j <= input.size(); j++) {
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            if (i != j && input[i - 1] == input[j - 1])
                dp[i][j] = max(dp[i - 1][j - 1] + 1, dp[i][j]);
        }
    cout << dp[input.size()][input.size()] << endl;
    return 0;
}