-
Examples:
LCS for input Sequences “ABCDGH” and “AEDFHR” is “ADH” of length 3.
LCS for input Sequences “AGGTAB” and “GXTXAYB” is “GTAB” of length 4.

 #include<bits/stdc++.h>
 
int max(int a, int b);
 
int lcs( char *X, char *Y, int m, int n )
{
   int L[m+1][n+1];
   int i, j;
 for (i=0; i<=m; i++)
   {
     for (j=0; j<=n; j++)
     {
       if (i == 0 || j == 0)
         L[i][j] = 0;
 
       else if (X[i-1] == Y[j-1])
         L[i][j] = L[i-1][j-1] + 1;
 
       else
         L[i][j] = max(L[i-1][j], L[i][j-1]);
     }
   }
   
  //L[m][n] contains length of LCS for X[0..n-1] and Y[0..m-1]
   return L[m][n];
}
 
// Utility function to get max of 2 integers
int max(int a, int b)
{
    return (a > b)? a : b;
}
 
/* Driver program to test above function
int main()
{
  char X[] = "AGGTAB";
  char Y[] = "GXTXAYB";
 
  int m = strlen(X);
  int n = strlen(Y);
 
  printf("Length of LCS is %d", lcs( X, Y, m, n ) );
 
  return 0;
} 

Comments

Post a Comment

Popular posts from this blog

-
// sieve of Atkin is a popular way to find all the prime numbers in range using the dp approach and is //better than the erronthesis approach // C++ program for implementation of Sieve of Atkin #include <bits/stdc++.h> using namespace std;   int SieveOfAtkin(int limit) {     // 2 and 3 are known to be prime     if (limit > 2)         cout << 2 << " ";     if (limit > 3)         cout << 3 << " ";       // Initialise the sieve array with false values     bool sieve[limit];     for (int i = 0; i < limit; i++)         sieve[i] = false;     for (int x = 1; x * x < limit; x++) {         for (int y = 1; y * y < limit; y++) {                           // Main part of Sieve of Atkin             int n = (4 * x * x) + (y * y);             if (n <= limit && (n % 12 == 1 || n % 12 == 5))                 sieve[n] ^= true;               n = (3 * x * x) + (y * y);             if (n <= limit &
Read more

Linked List 10 operations from which problems are made ( complete guide for you)

-
/* These are the functions we will implement make your seatbelts tight and start progrmming cout<<" 1. Insert node at begining"<<endl; cout<<" 2. Append a node"<<endl; cout<<" 3. display the l.l"<<endl; cout<<" 4. Insert before a selected node"<<endl; cout<<" 5. Insert after a selected node "<<endl; cout<<" 6.Delete a particular node"<<endl; cout<<" 7.Reverse A L.L "<<endl; cout<<" 8. Do bot reverse the l.l but display the reversed order (using recursion)"<<endl; cout<<"9. find middle element in a list using slow and fast pointer"<<endl; cout<<"10. check if linked list is palindrome or not (we know if even f=NULL odd f->next=NULL)"<<endl; cout<<" 11. exit"<<endl; */ #include<iostream> using namespace std; struct node{
Read more

Stack - print bracket number

-
/ * example 2 (0+1)*0(0+1)*0(0+1)* (1*0)*1* o/p 1 1 2 2 3 3  1 1  Example: Input: 3 (a+(b*c))+(d/e) ((())(())) ((((() Output: 1 2 2 1 3 3 1 2 3 3 2 4 5 5 4 1 1 2 3 4 5 5 */ #include<bits/stdc++.h> using namespace std; int main()  { int t; cin>>t; while(t--) {     string s;     stack <int> st;     int c=0; // we maintain the count of open brackets     cin>>s;     for(int i=0;i<s.length();i++)     {         if(s[i]=='(')         {c++;         cout<<c<<" ";         st.push(c);         }         if(s[i]==')')         {             cout<<st.top()<<" ";             st.pop();         }     }     cout<<endl; } return 0; }
Read more