Computer Science: 5th sem ADA Lab Program 11

Analysis and Design of Algorithms Lab.

Question 11.

//Implement Horsepool algorithm for string matcing
//Find the binomial Co-efficient using dynamic programing

#include<iostream>
#include <conio.h>
#include <string.h>
using namespace std;

void shiftTable(int *tab,int m,char *p,int n)
{
for(int i=0;i<m;i++)
tab[i]=n;
for(int i=0;i<n-1;i++)
{
tab[p[i]]=n-1-i;
}

}

int horsepool(char *arr,char *pattren)
{
int table[128];
int n=strlen(arr);
int m=strlen(pattren);
int k=0;
shiftTable(table,128,pattren,m);

for(int i=m-1;i<=n-1;)
{

for(k=0;arr[i-k]==pattren[m-1-k];k++);

if(k==m)
return i-m+1;

i+=table[arr[i]];
}

return -1;
}

int binomial(int n,int r)
{
if(n==0||r==0||n==r)
return 1;
else
return binomial(n-1,r-1)+binomial(n-1,r);
}

void main()
{
cout<<"Enter the string:";
char *str=new char[100];cin>>str;
cout<<"Enter the pattren:";
char *pat=new char[100];cin>>pat;
int index=horsepool(str,pat);
if(index==-1)
cout<<"\nString NOT found";
else
cout<<"\nString found at:"<<index;


cout<<"\n\nEnter the valut of n and r for binomial coefficient:";
int n,r;cin>>n>>r;
cout<<"Binomial coefficient of "<<n<<"C"<<r<<"="<<binomial(n,r);

getch();
}