AIBOHP - Aibohphobia Editorial - SPOJ - UCS - Unleash-Coding-Skills

Saturday, 12 May 2018

AIBOHP - Aibohphobia Editorial - SPOJ - UCS

AIBOHP - Aibohphobia


The link for the problem AIBOHP - Aibohphobia is:

This is a dynamic programming problem. The solution for AIBOHP - Aibohphobia:


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

long int lcs(string s1,string s2)
{
      long int a[7000][7000];
        long int i,j;
      for(i=0;i<=s1.length();i++)
      {
            for(j=0;j<=s2.length();j++)
            {
                  if(i==0||j==0)
                  {
                        a[i][j]=0;
                  }
                  else if(s1[i-1]==s2[j-1])
                  {
                        a[i][j]=a[i-1][j-1]+1;
                  }
                  else
                  {
                        a[i][j]=max(a[i-1][j],a[i][j-1]);
                  }
            }
      }
   return s1.length()-a[s1.length()][s2.length()];
}

int main() {
      long int t;
      string s1,s2;
      cin>>t;
      for(int ii=0;ii<t;ii++)
      {
      cin>>s2;
      s1=s2;
      reverse(s1.begin(),s1.end());
      long int rem=lcs(s1,s2);
      cout<<rem<<endl;
}
 return 0;
}


Helper Tags:
AIBOHP - Aibohphobia .... AIBOHP - Aibohphobia ... AIBOHP - Aibohphobia ... AIBOHP - Aibohphobia ... AIBOHP - Aibohphobia ... AIBOHP - Aibohphobia  ... AIBOHP - Aibohphobia .. 
AIBOHP - Aibohphobia .. AIBOHP - Aibohphobia  ... AIBOHP - Aibohphobia .. 

No comments:

Post a comment