ronith
10/24/2018 - 6:27 AM

Print the longest common substring

It is based on the dynamic programming implementation explained in this post. The longest suffix matrix LCSuff[][] is build up and the index of the cell having the maximum value is tracked. Let that index be represented by (row, col) pair. Now the final longest common substring is build with the help of that index by diagonally traversing up the LCSuff[][] matrix until LCSuff[row][col] != 0 and during the iteration obtaining the characters either from X[row-1] or Y[col-1] and adding them from right to left in the resultant common string.

Print the longest common substring.cpp
content_copyfile_download
//https://www.geeksforgeeks.org/print-longest-common-substring/
#include <bits/stdc++.h>
using namespace std;

void func(string s, string t) {
    int n=s.length(), m= t.length();
    int dp[n+1][m+1];

    int ans=INT_MIN, r,c;

    for (int i=0;i<=n;i++) {
        for (int j=0;j<=m;j++) {
            if (i==0 || j==0)
                dp[i][j]=0;
            else if (s[i]==t[j]) {
                dp[i][j]= 1+ dp[i-1][j-1];
                if (ans < dp[i][j]) {
                    ans= dp[i][j];
                    r= i;
                    c= j;
                }
            }
            else
                dp[i][j]= 0;
        }
    }
    cout<< "Length of LCS: "<< ans;
    string str;
    while (dp[r][c]!=0) {
        str+= s[r];
        r--;
        c--;
    }
    reverse(str.begin(), str.end());
    cout<<"\nLCS is: "<< str;
}

int main() {
    string s= "OldSite:GeeksforGeeks.org";
    string t= "NewSite:GeeksQuiz.com";

    func(s,t);
}