Finite Automata String Matching Algorithm using c

Finite Automata String Matching Algorithm

# include <iostream.h>

# include <conio.h>

# include <string.h>

class FiniteAutomaton

{

       private:

                       char *T,*P,*sig;

                       int n,m,l,q,trans[15][15];

       public :

                       void begin(void);

                       void set_trans(void);

                       int tfunc(char);

                       void matcher(void);

                       int check(int,int);

};

void FiniteAutomaton :: begin()

{

       int i=0,j=0;

       l=0; m=0; n=0; q=0;

       cout<<"\n\n Enter the input text :";

       cin>>T;

       cout<<"\n\n Enter the pattern :";

       cin>>P;

       n=strlen(T);

       m=strlen(P);

       while (T[i]!='\0') {

                       for (j=0;j<l;j++)  
                      {

                                       if (T[i]==sig[j])

                                                       break;

                       }

                       if (j==l)                 
                      {

                                       sig[l]=T[i];

                                       l++;

                       }

                       i++;

       }

       sig[l]='\0';

       for (i=0;i<15;i++)

       {

                       for (j=0;j<15;j++)

                       {

                                       trans[i][j]=0;

                       }

       }

       cout<<sig;

}

void FiniteAutomaton :: set_trans()

{

       int i,j=0,k=0;

       for (i=0;i<=m;i++)
                       {

                        while (sig[j]!='\0') {

                                       (q+2)>(m+1)?k=m+1:k=q+2;

                                       do 
                                       {

                                                       k--;

                                       }
                                       while (check(k,j));

                                       j++;

                        }

       }

}

int FiniteAutomaton:: check(int k,int u)

{

       int i;

       for (i=k;i>=0;i--) 
       {

       }

}

int FiniteAutomaton :: tfunc(char a)

{

       int i;

       for (i=0;i<l;i++) 
       {

                       if (sig[i]==a)

                       break;

       }

       return(trans[q][i]);

}

void FiniteAutomaton :: matcher()

{

       int i;

       for (i=0;i<n;i++)               
      {

                       if (tfunc(T[i])==m)

                       cout<<"\n\n The string is found at shift s = "<<i;

       }

}

void main()

{

       FiniteAutomaton fa;

       clrscr();

       fa.begin();

       getch();

}

Rabin-karp String Matching Algorithm using c

//Rabin karp String Matching Algorithm using c language 

#include<stdio.h>

#include<conio.h>

#include<string.h>

#include<math.h>

#define d 10

void RabinKarpStringMatch(char *, char *, int);

void main()

{

       char *Text, *Pattern;

       int Number = 11; //Prime Number

       clrscr();

       printf("\nEnter Text String : ");

       gets(Text);

       printf("\nEnter Pattern String : ");

       gets(Pattern);

       RabinKarpStringMatch(Text,Pattern,Number);

       getch();

}

void RabinKarpStringMatch(char *Text, char *Pattern, int Number)

{

       int M,N,h,P=0,T=0, TempT, TempP;

       int i,j;

       M = strlen(Pattern);

       N = strlen(Text);

       h = (int)pow(d,M-1) % Number;

       for(i=0;i<M;i++)  {

                       P = ((d*P) + ((int)Pattern[i])) % Number;

                       TempT = ((d*T) + ((int)Text[i]));

                       T =  TempT % Number;

       }

       for(i=0;i<=N-M;i++)  {

                       if(P==T)  {

                                       for(j=0;j<M;j++)

                                                       if(Text[i+j] != Pattern[j])

                                                                       break;

                                       if(j == M)

                                                       printf("\nPattern Found at Position :  %d",i+1);

                       }

                       TempT =((d*(T - Text[i]*h)) + ((int)Text[i+M]));

                       T = TempT % Number;

                       if(T<0)

                                       T=T+Number;

       }

}

knapsack algorithm using c++

#include<iostream.h>

struct kru

{

  int i,p,w;

  float pr;

}g[10];

void main()

{

int n,j,k,wa;

float total=0;

struct kru temp;

cout<<"enter data ow W";

cin>>wa;

cout<<"Enter no.of nodes";

cin>>n;

cout<<"Enter for sum of calculation:";

for(j=0;j<n;j++)

{

g[j].i=j+1;

cout<<"i th profit =";

cin>>g[j].p;

cout<<"i th weight =";

cin>>g[j].w;

}

for(j=0;j<n;j++)

{

g[j].pr=g[j].p/float(g[j].w);

}

for(j=0;j<n;j++)

{

for(k=0;k<n;k++)

{

 if(g[j].pr<=g[k].pr)

 {

  temp=g[j];

  g[j]=g[k];

  g[k]=temp;

 }

}

}

for(j=0;j<n;j++)

{

  if(wa>=g[j].w)

  {

  total=total+g[j].p;

  wa=wa-g[j].w;

  }

  total=total+(g[j].pr*wa);

}

cout<<"total is "<<total;

}

merge short

#include<stdio.h>
#define MAX 50

void mergeSort(int arr[],int low,int mid,int high);
void partition(int arr[],int low,int high);

int main(){

    int merge[MAX],i,n;

    printf("Enter the total number of elements: ");
    scanf("%d",&n);

    printf("Enter the elements which to be sort: ");
    for(i=0;i<n;i++){
         scanf("%d",&merge[i]);
    }

    partition(merge,0,n-1);

    printf("After merge sorting elements are: ");
    for(i=0;i<n;i++){
         printf("%d ",merge[i]);
    }

   return 0;
}

void partition(int arr[],int low,int high){

    int mid;

    if(low<high){
         mid=(low+high)/2;
         partition(arr,low,mid);
         partition(arr,mid+1,high);
         mergeSort(arr,low,mid,high);
    }
}

void mergeSort(int arr[],int low,int mid,int high){

    int i,m,k,l,temp[MAX];

    l=low;
    i=low;
    m=mid+1;

    while((l<=mid)&&(m<=high)){

         if(arr[l]<=arr[m]){
             temp[i]=arr[l];
             l++;
         }
         else{
             temp[i]=arr[m];
             m++;
         }
         i++;
    }

    if(l>mid){
         for(k=m;k<=high;k++){
             temp[i]=arr[k];
             i++;
         }
    }
    else{
         for(k=l;k<=mid;k++){
             temp[i]=arr[k];
             i++;
         }
    }

    for(k=low;k<=high;k++){
         arr[k]=temp[k];
    }
}


Sample output:

Enter the total number of elements: 5
Enter the elements which to be sort: 2 5 0 9 1
After merge sorting elements are: 0 1 2 5 9

quick sort using c

#include<stdio.h>

void quicksort(int [10],int,int);

int main(){
  int x[20],size,i;

  printf("Enter size of the array: ");
  scanf("%d",&size);

  printf("Enter %d elements: ",size);
  for(i=0;i<size;i++)
    scanf("%d",&x[i]);

  quicksort(x,0,size-1);

  printf("Sorted elements: ");
  for(i=0;i<size;i++)
    printf(" %d",x[i]);

  return 0;
}

void quicksort(int x[10],int first,int last){
    int pivot,j,temp,i;

     if(first<last){
         pivot=first;
         i=first;
         j=last;

         while(i<j){
             while(x[i]<=x[pivot]&&i<last)
                 i++;
             while(x[j]>x[pivot])
                 j--;
             if(i<j){
                 temp=x[i];
                  x[i]=x[j];
                  x[j]=temp;
             }
         }

         temp=x[pivot];
         x[pivot]=x[j];
         x[j]=temp;
         quicksort(x,first,j-1);
         quicksort(x,j+1,last);

    }
}

Output:
Enter size of the array: 5
Enter 5 elements: 3 8 0 1 2
Sorted elements: 0 1 2 3 8

gcd using c++

#include<iostream.h>
int gcd(int x,int y)
{
if(x==y)
return (x);
else
{
if(x>y)
gcd(x-y,y);
else
gcd(x,y-x);
}
}
void main()
{
int n1,n2,g;
cin>>n1>>n2;
g=gcd(n1,n2);
cout<<"gcd of "<<n1<<" & "<<n2<<" is :"<<g;
}