DYNAMIC LCS

 #include<iostream>

using namespace std;

int lcs(string pattern_1, string pattern_2) {

  int m = pattern_1.size();

  int n = pattern_2.size();

  // dp will store solutions as the iteration goes on

  int dp[n + 1][m + 1];

  for (int i = 0; i < n + 1; i++) {

    for (int j = 0; j < m + 1; j++) {

      if (i == 0 || j == 0) {

        dp[i][j] = 0;

      } else if (pattern_2[i - 1] == pattern_1[j - 1]) {

        dp[i][j] = dp[i - 1][j - 1] + 1;

      } else {

        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

      }

    }

  }

  return dp[n][m];

}

int main() {

  string pattern_1 = "RGBGARGA";

  string pattern_2 = "BGRARG";

  cout<<"Length of LCS: "<<lcs(pattern_1, pattern_2)<<endl;

}