Showing posts with label 2nd semester. Show all posts
Showing posts with label 2nd semester. Show all posts

Sunday 17 July 2016

Program 5: Rabin Karp String Matching

MTech VTU Advanced Algorithm Lab (2nd sem)

Design, develop, and write a program to solve String matching problem using Rabin Karp algorithm and determine its performance.

#include<stdio.h>
#include<string.h>
#define d 256

void search(char pat[], char txt[], int q)
{
            int M = strlen(pat);
            int N = strlen(txt);
            int i, j;
            int p = 0;
            int t = 0;
            int h = 1;

            for (i = 0; i < M-1; i++)
                        h = (h*d) % q;
            for (i = 0; i < M; i++)
            {
                        p = (d*p + pat[i]) % q;
                        t = (d*t + txt[i]) % q;
            }
            for (i = 0; i <= N - M; i++)
            {
                    if ( p == t )
                    {
                                for (j = 0; j < M; j++)
                                    {
                                                if (txt[i+j] != pat[j])
                                                            break;
                                    }
                                   if (j == M)
                                                printf("\nPattern found at index %d", i);
                        }

                        if ( i < N-M )
                        {
                                    t = (d*(t - txt[i]*h) + txt[i+M]) % q;
                                    if (t < 0)
                                                t = (t + q);
                        }
            }
}

int main()
{
            char txt[30], pat[30];
            int q = 101; // A prime number
            printf("\n Enter the text:");
            gets(txt);
            printf("\n Enter the pattern:");
            gets(pat);
            search(pat, txt, q);
            return 0;
}

Output:
 Enter the text: abacbaaababa
 Enter the pattern: aba

Pattern found at index 0
Pattern found at index 7
Pattern found at index 9

Program 4: Finite Automata string matching

MTech VTU Advanced Algorithm Lab (2nd sem)

Design, develop, and write a program to solve String matching problem using Finite Automata and determine its performance.


#include<stdio.h>
#include<string.h>
#define CHARS 256

int getNextState(char pat[30], int M, int state, int x)
{
            int ns, i;
            if (state < M && x == pat[state])
                        return state+1;
            for (ns = state; ns > 0; ns--)
            {
                        if(pat[ns-1] == x)
                        {
                                    for(i = 0; i < ns-1; i++)
                                    {
                                                if (pat[i] != pat[state-ns+1+i])
                                                break;
                                    }
                                    if (i == ns-1)
                                                return ns;
                        }
            }
            return 0;
}

void computeTF(char pat[30], int M, int TF[][CHARS])
{
            int state, x;
            for (state = 0; state <= M; ++state)
                        for (x = 0; x < CHARS; ++x)
                                    TF[state][x] = getNextState(pat, M,  state, x);
}

void search(char pat[30], char txt[30])
{
            int M = strlen(pat);
            int N = strlen(txt);
            int TF[M+1][CHARS];
            int i, state=0;
            computeTF(pat, M, TF);
           for (i = 0; i < N; i++)
            {
                        state = TF[state][txt[i]];
                        if (state == M)
                        {
                                    printf ("\nPattern found at index %d", i-M+1);
                        }
            }
}

int main()
{
            char txt[30], pat[30];
            printf("\nEnter the text:");
            gets(txt);
            printf("\nEnter the pattern:");
            gets(pat);
            search(pat, txt);
            return 0;
}


Output:

Case 1:
Enter the text: ababacabaabcaba
Enter the pattern: aba
Pattern found at index 0
Pattern found at index 2
Pattern found at index 6
Pattern found at index 12


Case 2:
Enter the text: abababacaba
Enter the pattern: ababaca
Pattern found at index 2

Program 3: Naive and KMP

MTech VTU Advanced Algorithm Lab (2nd sem)

Design, develop, and write a program to solve string matching problem using naïve approach and the KMP algorithm. Compare their performances.

#include<stdio.h>
#include<string.h>
int NaiveString(char t[30],char p[30], int n, int m);
int KMP(char t[30],char p[30], int n, int m);

int main()
{
            int n, m;
            char p[15], t[50];
            printf("\n Enter the text:");
            gets(t);
            printf("\n Enter the pattern:");
            gets(p);
            n = strlen(t);
            m = strlen(p);
           
           printf("\nNaive String Algorithm: ");
            NaiveString(t, p, n, m);
            printf("\n\n\nKMP String Algorithm: ");
            KMP(t, p, n, m);
}

int NaiveString(char t[30], char p[30], int n, int m)
{
            int i, j, found=0;
            for(i = 0; i < =n-m; i++)
            {
                        for(j = 0; j < m; j++)
                         {
                                    if(t[i+j] != p[j])
                                                break;
                        }
                        if(j == m)
                        {
                                 printf("\n   The pattern found at position:%d", i+1);
                                 found = 1;
                        }
             }
              if(found == 0)
                        printf("\n   Pattern not found");
}

int KMP(char t[30], char p[30], int n, int m)
{
            int pi[25];
            int i, k, flag = 1;
            pi[0] = 0, k = 0;
            for(i = 1; i < m; i++)
            {
                        while((k>0) && (p[k] != p[i]))
                                    k = pi[k-1];
                        if(p[k] == p[i])
                                    k++;
                        pi[i] = k;
            }

            printf("\nPI[] array is as follows:\n");
            for(i = 0; i < m; printf("\nPI[%d] = %d", i, pi[i]), i++);
            k = 0;
            for(i = 0; i < n; i++)
            {
                        while(k>0 && (p[k] != t[i]))
                                    k = pi[k-1];
                        if(p[k] == t[i])
                                    k++;
                        if(k == m)
                        {
                                    flag = 0;
                                    printf("\n  Pattern match occurs at position %d:", i-m+2);
                                    k = pi[k-1];
                         }
            }
            if(flag == 1)
                        printf("\n Pattern not found!!!\n\n");
            return 0;
}


Output:

Case 1:
Enter the text: bacbabababacaca
Enter the pattern: ababaca
Naive String Algorithm:
   The pattern found at position: 7

KMP String Algorithm:
PI[] array is as follows:
PI[0] = 0
PI[1] = 0
PI[2] = 1
PI[3] = 2
PI[4] = 3
PI[5] = 0
PI[6] = 1
    Pattern match occurs at position: 7


Case 2:
Enter the text: aabaacaadaabaaabaa
Enter the pattern: aaba
Naive String Algorithm:
   The pattern found at position:1
   The pattern found at position:10
   The pattern found at position:14

KMP String Algorithm:
PI[] array is as follows:
PI[0] = 0
PI[1] = 1
PI[2] = 0
PI[3] = 1
  Pattern match occurs at position: 1
  Pattern match occurs at position: 10
  Pattern match occurs at position: 14

Program 2: Monte Carlo Algorithm

MTech VTU Advanced Algorithm Lab (2nd sem)

Design, develop, and write a program to implement a Monte Carlo algorithm to test the primality of a given integer and determine its performance.

#include<stdio.h>
#include<stdlib.h>
int Modular_Exponentiation(int, int, int);
void Binary(int, int *, int *);

int main()
{
            int n, res;
            printf("\n Enter a no n:");
            scanf("%d", &n);
            if(n <= 0)
            {
                        printf("\n Please enter a +ve number!!!");
                        exit(0);
            }
            res = Modular_Exponentiation(2,n-1,n);
            if(n == 1)
                        printf("\n %d is prime!!!", n);
            else if((res % n) == 1)
                        printf("\n %d is prime!!!", n);
            else
                        printf("\n %d is not prime!!!", n);
            return 0;
}

int Modular_Exponentiation(int a, int b, int n)
{
            int c, d, bin[20] = {0}, k, i;
            c=0, d=1;
            Binary(b, bin, &k);
            for(i = k; i >= 0; i--)
            {
                        c = 2*c;
                        d = (d*d) % n;
                        if(bin[i] == 1)
                        {
                                    c++;
                                    d = (d*a) % n;
                        }
                        printf("\n i=%d, bi=%d, c=%d, d=%d", i, bin[i], c, d);
            }
            return d;
}

void Binary(int b, int *bin, int *k)
{
            int i = 0, n = b;
            *k = 0;
            *bin = 0;
            while(b != 0)
            {
                        bin[i] = b % 2;
                        *k = *k+1;
                        b /= 2;
                        i++;
            }
            *k = *k-1;
            printf("\n Binary equivalent of %d is:", n);
            for(i = *k; i >= 0; printf("%5d", bin[i--]) );
}


Output:

Case 1:
 Enter a no n:
 Binary equivalent of 4 is:    1    0    0
 i=2, bi=1, c=1, d=2
 i=1, bi=0, c=2, d=4
 i=0, bi=0, c=4, d=1
 5 is prime!!!

Case 2:
 Enter a no n:9
 Binary equivalent of 8 is:    1    0    0    0
 i=3, bi=1, c=1, d=2
 i=2, bi=0, c=2, d=4
 i=1, bi=0, c=4, d=7
 i=0, bi=0, c=8, d=4
 9 is not prime!!!