Programmer's Blog

Programmer's reference

[C++] (LCS) Longest common sequence problem

 string k = String1;
 string g = String2;
 k.insert(0,1,' ');
 g.insert(0,1,' ');
 
 int m = k.length();
 int n = g.length();
 int arr[m][n];
 
 for (int i = 0 ; i < m ; i++) arr[i][0] = 0;
 for (int j = 0 ; j < n ; j++) arr[0][j] = 0;
 
 for (int i = 1 ; i < m ; i++ )
 {
     for (int j = 1 ; j < n ; j++)
     {
         if (k[i] == g[j])
         {
             arr[i][j] = arr[i-1][j-1] + 1;
         }
         else
         {
             arr[i][j] = arr[i][j-1] > arr[i-1][j] ? arr[i][j-1] : arr[i-1][j];
         }
     }
 } 
 
 cout << arr[m-1][n-1] << endl;
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: