Program In C++ To Implement Naive String Matching Algorithm

#include<iostream.h>
#include<conio.h>
void naive(int t[],int p[],int n,int m)
{
 int s,flag=0,i,j;
 for(s=0;s<=(n-m);s++)
{
 for(i=s+1;i<=s+m;i++)
 {
  for(j=1;j<=m;j++)
  {
   if(t[s+j]==p[j])
    {
     flag=1;
     continue ;
    }
   else
   {
    flag=0;
    break;
   }
  }
 }
 if(flag==1)
  {
   cout<<"\nPattern Occurs With Shift: "<<s<<"\n";
  }
 }
}

void main()
{ clrscr();
int p[100],t[20];
int m,n,i;
cout<<"Enter Length Of Text : ";
cin>>n;
cout<<"\nEnter Text : ";
for(i=1;i<=n;i++)
{ cin>>t[i]; }
cout<<"\nEnter Length Of Pattern: ";
cin>>m;
cout<<"\nEnter Pattern: ";
for(i=1;i<=m;i++)
{ cin>>p[i]; }
naive(t,p,n,m);
getch();
}

Program In C++ To Find Maximum And Minimum In 2D Array

#include<iostream.h>
#include<conio.h>
void main()
{ clrscr();
int a[20][20],m,n,i,j,max,min;
cout<<"Enter Number Of Rows In Array: ";
cin>>m;
cout<<"\nEnter Number Of Columns In Array: ";
cin>>n;
cout<<"\nEnter Array: ";
for(i=0;i<m;i++)
{ for(j=0;j<n;j++)
{ cin>>a[i][j]; }
}
min=max=a[0][0];
cout<<"\nMatrix Entered Is: \n";
for(i=0;i<m;i++)
{ for(j=0;j<n;j++)
{ cout<<a[i][j]<<"  ";
if(a[i][j]<min)
min=a[i][j];
if(a[i][j]>max)
max=a[i][j];
}
cout<<"\n"; }
cout<<"\nMinimum In The Array Is: "<<min;
cout<<"\nMaximum In The Array Is: "<<max;
getch();
}

Program In C++ To Find Maximum And Minimum In 1D Array

#include<iostream.h>
#include<conio.h>
void main()
{ clrscr();
int a[20],n,i,max,min;
cout<<"\nEnter Size Of Array: ";
cin>>n;
cout<<"\nEnter Array: ";
for(i=0;i<n;i++)
cin>>a[i];
max=min=a[0];
for(i=0;i<n;i++)
{ if(a[i]<min)
min=a[i];
if(a[i]>max)
max=a[i];
}
cout<<"\nMinimum In Array Is: "<<min;
cout<<"\nMaximum In Array Is: "<<max;
getch();
}

Program In C++ for quicksort sort and its time complexity

#include<iostream.h>
#include<conio.h>
#include<time.h>
#include<dos.h>
int Partition(int a[],int p,int r)
{ int tmp,x=a[r];
int i=p-1;
for(int j=p;j<r;j++)
if(a[j]<x)
{ i++;
tmp=a[i];
a[i]=a[j];
a[j]=tmp; }
tmp=a[i+1];
a[i+1]=a[r];
a[r]=tmp;
return i+1; }
void quicksort(int a[],int p,int r)
{ int q;
if(p<r)
 { q=Partition(a,p,r);
quicksort(a,p,q-1);
quicksort(a,q+1,r); }}

int main()
{ clrscr();
int a[10],n,i,j,tmp;
clock_t start,end;
cout<<"Enter Array Size: ";
cin>>n;
cout<<"\nEnter Array: ";
for(i=0;i<n;i++)
{ cin>>a[i]; }
start=clock();
quicksort(a,0,n-1);
delay(100);
end=clock();
cout<<"\nArray After Sorting Is: ";
for(i=0;i<n;i++)
{ cout<<a[i]<<"\t"; }
cout<<"\nTime Taken Is: "<<(end-start)/CLK_TCK<<" seconds";
getch();
return 0;
}

Program In C++ for merge sort and its time complexity

#include<iostream.h>
#include<conio.h>
#include<time.h>
#include<dos.h>
#include<limits.h>
void merge(int a[],int p,int q,int r)
{int i,j;
int n1=q-p+1;
int n2=r-q;
int L[6];int R[6];
for(i=0;i<n1;i++)
  L[i]=a[p+i];
for(j=0;j<n2;j++)
  R[j]=a[q+j+1];
 L[n1]=INT_MAX;
 R[n2]=INT_MAX;
 i=0;j=0;
 for(int k=p;k<=r;k++)
 { if(L[i]<R[j])
   { a[k]=L[i];
     i++; }
   else
   { a[k]=R[j];
     j++;
   }
 }
}
void mergesort(int a[],int p,int r)
{ int q;
if(p<r)
{ q=(p+r)/2;
mergesort(a,p,q);
mergesort(a,q+1,r);
merge(a,p,q,r);
 }
}
void main()
{ clrscr();
int a[10],n,i;
clock_t start, end;
cout<<"\nEnter The Size Of Array: ";
cin>>n;
cout<<"\nEnter The Array: ";
for(i=0;i<n;i++)
cin>>a[i];
start=clock();
mergesort(a,0,n-1);
delay(200);
end=clock();
cout<<"\nArray After Sorting Is: ";
for(i=0;i<n;i++)
cout<<a[i]<<"\t";
cout<<"\nTime Taken Is: "<<(end-start)/CLK_TCK;
getch();
}

Program In C++ to find time complexity of binary search

#include<iostream.h>
#include<conio.h>
#include<time.h>
#include<dos.h>
int main()
{  clock_t start,end;
start=clock();
clrscr();
int a[10],n,beg,last,mid,ele,flag=-1;
cout<<"Enter size of array: (SORTED)";
cin>>n;
cout<<"\nEnter Array: ";
for(int i=0;i<n;i++)
{ cin>>a[i];
}
cout<<"\nEnter The Element To Be Searched: ";
cin>>ele;
beg=0;last=n;
while(beg!=last)
{ mid=(beg+last)/2;
if(a[mid]==ele)
{ cout<<"Element Found At Position: "<<mid+1;
flag=0;
break;}
else if(a[mid]<ele)
{ beg=mid-1; }
else
last=mid+1;
}
if(flag==-1)
cout<<"Element Not Found In The Array !!!!";
delay(2000);
end=clock();
cout<<"\nTime Taken Is: "<<(end-start)/CLK_TCK;
getch();
return 0;

}

Program In C++ to find time complexity of linear search

#include<iostream.h>
#include<conio.h>
#include<time.h>
#include<dos.h>
int main()
{ clock_t start,end;
start=clock();
clrscr();
int a[10],n,ele,pos;
cout<<"Enter size of array: ";
cin>>n;
cout<<"\nEnter Array: ";
for(int i=0;i<n;i++)
{ cin>>a[i]; }
cout<<"\nEnter The Element To Be Searched: ";
cin>>ele;
for(i=0;i<n;i++)
{ if(a[i]==ele)
{ cout<<"\nElement Found At Positon: "<<i+1;
break; }
if(i==n-1)
{ cout<<"\nElement Not Found In Given Array !!!";
} }
delay(200);
end=clock();
cout<<"\nTime Taken Is: "<<(end-start)/CLK_TCK;
getch();
return 0;
}

Program In C++ To Find Longest Common Sub sequence (LCS)

#include<iostream.h>
#include<conio.h>
#include<process.h>
int b[100][100],c[100][100];
void PRINT_LCS(int b[100][100],int x[],int i,int j)
{
 if(i==0||j==0)
 {return;}
 if(b[i][j]==0)
 {
  PRINT_LCS(b,x,i-1,j-1);
  cout<<x[i]<<"\t";
 }
  else if(b[i][j]==1)
  {
   PRINT_LCS(b,x,i-1,j);
  }
  else
  {
   PRINT_LCS(b,x,i,j-1);
  }
}

void LCS_LENGTH(int x[], int y[],int lenx,int leny)
{
 int i,j,b[100][100],c[100][100],m=lenx,n=leny;

 for(i=0;i<=m;i++)
 {c[i][0]=0;}

 for(j=0;j<=n;j++)
 {c[0][j]=0;}

 for(i=1;i<=m;i++)
 {
  for(j=1;j<=n;j++)
  {
   if(x[i]==y[j])
   {
    c[i][j]=c[i-1][j-1]+1;
    b[i][j]=0;
   }
   else if(c[i-1][j]>=c[i][j-1])
   {
    c[i][j]=c[i-1][j];
    b[i][j]=1;
   }
   else
   {
    c[i][j]=c[i][j-1];
    b[i][j]=2;
   }
  }
 }
 PRINT_LCS(b,x,lenx,leny);
}
void main()
{ clrscr();
 int x[100],y[100],lenx,leny;
 cout<<"Enter the length of first sequence(x) : ";
 cin>>lenx;
 cout<<"Enter x";
 for(int i=1;i<=lenx;i++)
 cin>>x[i];
 cout<<"Enter the length of second sequence(y) : ";
 cin>>leny;
 cout<<"Enter y";
 for(int j=1;j<=leny;j++)
 cin>>y[j];
 cout<<"\nLongest Common Subsequence Is: ";
 LCS_LENGTH(x,y,lenx,leny);
 getch();
}