string-search.c

/******************************************************************************

Welcome to GDB Online.
GDB online is an online compiler and debugger tool for C, C++, Python, PHP, Ruby, 
C#, VB, Perl, Swift, Prolog, Javascript, Pascal, HTML, CSS, JS
Code, Compile, Run and Debug online from anywhere in world.

https://onlinegdb.com/-sj3UGJm9

*******************************************************************************/
#include <stdio.h>
#include <string.h>

// d is the number of characters in the input alphabet 
#define d 256

void optimizedNaivePatternSearch(char* pat, char* txt) {
    int M = strlen(pat);
    int N = strlen(txt);
    
    int i = 0;
    
    while (i <= N - M) {
        int j;
        
        for (j = 0; j < M; j++)
            if (txt[i + j] != pat[j])
                break;
                
        if (j == M) {
            printf("optimizedNaivePatternSearch Pattern found at index %d\n", i);
            i = i + M;
        } else if (j == 0)
            i++;
        else
            i += j;
    }
    
}

void naivePatternSearch(char * pat, char * txt) {
    int M = strlen(pat);
    int N = strlen(txt);
    
    for (int i = 0; i <= N - M; i++) {
        int j;
        
        for (j = 0; j < M; j++) {
            //printf("text letter: %c and pattern letter: %c\n", txt[i + j], pat[j]);
            if (txt[i + j] != pat[j])
                break;
        }
        
        if (j == M)
            printf("naivePatternSearch Pattern found in text at index %d\n", i);
    }
}

void computeLPSArray(char* pat, int M, int* lps) {
    // length of the previous longest prefix suffix
    int len = 0; 
  
    lps[0] = 0; // lps[0] is always 0 
  
    // the loop calculates lps[i] for i = 1 to M-1 
    int i = 1;
    
    while (i < M) {
        if (pat[i] == pat[len]) { 
            len++;
            lps[i] = len; 
            i++; 
        } else {
            // This is tricky. Consider the example. 
            // AAACAAAA and i = 7. The idea is similar 
            // to search step. 
            if (len != 0) { 
                len = lps[len - 1];
                // Also, note that we do not increment 
                // i here 
            } else /* if (len == 0) */ { 
                lps[i] = 0;
                i++;
            } 
        }
    }
}

void kmpPatternSearch(char* pat, char* txt) {
    int M = strlen(pat);
    int N = strlen(txt);
    
    // create lps[] that will hold the longest prefix suffix 
    // values for pattern
    int lps[M];
    
    // Preprocess the pattern (calculate lps[] array) 
    computeLPSArray(pat, M, lps);
    
    int i = 0; // index for txt[] 
    int j = 0; // index for pat[]
    
    while (i < N) {
        if (pat[j] == txt[i]) { 
            j++; 
            i++;
        }
        
        if (j == M) { 
            printf("kmpPatternSearch Found pattern at index %d\n", i - j); 
            j = lps[j - 1];
        } else if (i < N && pat[j] != txt[i]) { 
            // Do not match lps[0..lps[j-1]] characters, 
            // they will match anyway 
            if (j != 0) 
                j = lps[j - 1]; 
            else
                i = i + 1; 
        }
    }
}

void rabinKarpSearch(char* pat, char* txt, int q) {
    int M = strlen(pat);
    int N = strlen(txt);
    int i, j;
    int p = 0; // hash value for pattern
    int t = 0; // hash value for txt
    int h = 1;
    
    // The value of h would be "pow(d, M-1)%q"
    for (i = 0; i < M-1; i++)
        h = (h * d) % q;
  
    // Calculate the hash value of pattern and first
    // window of text
    for (i = 0; i < M; i++) {
        p = (d * p + pat[i]) % q;
        t = (d * t + txt[i]) % q;
    }
    
    printf("The value of h: %d\n", h);
    printf("hash value for pattern: %d\n", p);
    printf("hash value for txt: %d\n", t);
    
    // Slide the pattern over text one by one
    for (i = 0; i <= N - M; i++) {
        if (p == t) {
            /* Check for characters one by one */
            for (j = 0; j < M; j++) {
                if (txt[i + j] != pat[j])
                    break;
            }
            
            // if p == t and pat[0...M-1] = txt[i, i+1, ...i+M-1]
            if (j == M)
                printf("rabinKarpSearch Pattern found at index %d \n", i);
        }
        // Calculate hash value for next window of text: Remove
        // leading digit, add trailing digit
        if (i < N - M) {
            t = (d * (t - txt[i] * h) + txt[i + M]) % q;

            // We might get negative value of t, converting it
            // to positive
            if (t < 0)
                t = (t + q);
        }
    }
    
}

int main() {
    printf("Hello World\n");
    char txt[] = "AABAACAADAABAAABAA";
    char pat[] = "AABA";
    
    naivePatternSearch(pat, txt);
    
    kmpPatternSearch(pat, txt);
    
    // A prime number 
    int q = 101;
    
    rabinKarpSearch(pat, txt, q);
    
    optimizedNaivePatternSearch(pat, txt);
    return 0;
}