#include <stdio.h>
#include <string.h>
#include <stdlib.h>

// Structure with callback function and data for matches
typedef struct strmatch_s 
{
    void (*proc)(int, char *, struct strmatch_s *);
    int num_matches; 
} strmatch_t;

// This function gets called on every match
void proc_match(int i, char * s, strmatch_t * match) 
{
    printf("%.*s\n", 4, s);
    match->num_matches++;
}

// Return the maximum number of matched characters in two strings
inline int max_match(char * a, char * b, int n)
{
    int i = 0;
    while (a[i] == b[i] && i < n)
        i++;

    return i;
}

// Basic naive match: O(nm) time, no additional space
void strmatch_naive(char * p, char * t, strmatch_t * match)
{
    int n, m;
    n = strlen(p);
    m = strlen(t);

    // For every character in the string where we can match a pattern
    int i;
    for (i=0; i<m-n+1; i++) 
    {
        // Upon a match, call the callback function
        if (max_match(p, t+i, n) == n)
            match->proc(i, (char *)(t + i), match);
    }
}

// Basic naive way to calculate z-boxes
void zbox_naive(char * p, int n, int * z)
{
    // For every character in the pattern except the first
    int k;
    for (k=1; k < n; k++)
        z[k] = max_match(p, p+k, n);
}

typedef struct {
    int l;
    int r;
} zbox_t;

// Linear-time algorithm to calculate z-boxes
inline int zbox_linear_k(char * p, int n, int * z, int k, zbox_t * zb)
{
    int zk;
    // If we are calculating a z-value outside any known z-box
    if (k > zb->r)
    {
        // Do a naive match and adjust the r and l bounds
        zk = max_match(p, p+k, n);
        if (zk > 0)
        {
            zb->r = k + zk - 1;
            zb->l = k;
        }
    }
    else // Position k is contained within a z-box
    {
        // Calculate k's corresponding position in the prefix (kp)
        int kp = k - zb->l;

        // And the distance from k to the end of the z-box (b)
        int b = zb->r - k + 1;

        if (z[kp] < b)
            zk = z[kp];
        else 
        {
            int q = max_match(p+b, p+zb->r+1, n);
            zk = b+q;
            zb->r = k+zk - 1; 
            zb->l = k;
        }
    }
    return zk;
}

// Iterate through all k to calculate all z[k] to n (for the linear version)
void zbox_linear(char * p, int n, int * z)
{
    zbox_t zb = {.l=0, .r=0};
    int k;
    for (k=1; k<n; k++)
        z[k] = zbox_linear_k(p, n, z, k, &zb);
}

// Convenience for printing a z table
void printz(int * z, int n, char * p)
{
    int i; 
    printf("i\tz[i]\t%s\n", p);
    for (i=1; i<n; i++)
        printf("%u\t%u\n", i, z[i]);
}

// The simplest linear-time exact matching algorithm: O(m) time, O(n) space
void strmatch_linear(char * p, char * t, strmatch_t * match)
{
    int n, m;
    n = strlen(p);
    m = strlen(t);

    // Allocate space for needed z-values in the pattern and compute them
    int * z = calloc(n, sizeof(int));
    zbox_linear(p, n, z); 

    // Make concatenated string p$t (can be optimized out, but matches text)
    char * big = malloc(n+m+2);
    memcpy(big, p, n);      big[n] = '$';
    memcpy(big+n+1, t, m);  big[n+m+1] = '\0';

    // Now, for each index, i, in the text, calculate (but don't store) z[i]
    int i;
    zbox_t zb = {.l=0, .r=0};
    for (i=n+1; i<=n+m+1; i++) 
    {
        int zi = zbox_linear_k(big, n+m+1, z, i, &zb);
        if (i < n + 1)
            z[i] = zi;
        else
        {
            if(zi == n)
                match->proc(i - (n+1), (char *)(t + i - (n+1)), match);
        }
    }

    free(z);
}

// Calculates sp' for a pattern via the z-boxes
void spp_zbox(int * z, int * spp, int n)
{
    int i;
    for (i=0; i<n; i++)
        spp[i] = 0;

    // The end position of a z-box corresponds to a suffix
    int j;
    for (j=n-1; j > 1; j--)
    {
        i = j + z[j] - 1;
        spp[i] = z[j];
    }
}

// Calculates sp' for a pattern via the classic method
void spp_classic(int * spp, char * p, int n)
{
    int * sp = calloc(n, sizeof(int));
    sp[0] = 0;

    int k, v;
    char x;
    for (k=0; k < n-1; k++)
    {
        x = p[k+1];
        v = sp[k]; 

        while (p[v] != x && v != 0)
            v = sp[v];

        if(p[v] == x)
            sp[k+1] = v + 1;
        else
            sp[k+1] = 0;
 
    }

    spp[0] = 0;
    int i;
    for (i=1; i<n; i++)
    {
        v = sp[i];    
        if (i == n || p[v] != p[i+1])
            spp[i] = v;
        else
            spp[i] = (v == 0) ? 0 : spp[v-1];
    }

    free(sp);
}


// Knuth-Morris-Pratt (via z-box transformation or classic preprocessing)
void strmatch_kmp(char * p, char * t, strmatch_t * match)
{
    int n, m;
    n = strlen(p);
    m = strlen(t);
  
    // Right now, z exists separately and this can be optimized out
    int * z = calloc(n, sizeof(int));
    zbox_linear(p, n, z); 

    int * fp = calloc(n+1, sizeof(int));
    spp_zbox(z, fp, n);
    free(z);

    // Comment the top 5 statemets and uncomment these for KMP classic 
    // int * fp = calloc(n+1, sizeof(int));
    // spp_classic(fp, p, n);

    // Preprocess p to obtain f'
    int k;
    for (k=n; k >= 0; k--)
    {
        if (k == 0)
            fp[k] = 1;
        else 
            fp[k] = fp[k-1];
    }

    // Run the algorithm
    int pi, ti;
    pi = ti = 0;
    while (ti + (n-pi) <= m)
    {
        while (p[pi] == t[ti] && pi < n)
        {
            pi++; 
            ti++;
        }

        // We have a match!
        if (pi == n)
        {
            int midx = ti - n;
            match->proc(midx, (char *)(t + midx), match);
        }

        if (pi == 0)
            ti++;
       
        // Perform the correct skip 
        pi = fp[pi];
    }

    free(fp);
}

// Reverse a string in place
void strrev(char * s)
{
    int i, n;
    char tmp;
    n = strlen(s);
    for (i=0; i<n/2; i++)
    {
        tmp = s[i];
        s[i] = s[n-i-1];
        s[n-i-1] = tmp;
    }
}

typedef struct rlist_s {
    int pos;
    struct rlist_s * next;
} rlist_t;

// Boyer-Moore via strong good suffix rule z-box transformation
void strmatch_bm(char * p, char * t, strmatch_t * match)
{
    int n, m;
    n = strlen(p);
    m = strlen(t);
    char * pr = strdup(p);
    strrev(pr);

    // Preprocessing variables (avoiding several minor optimizations here)
    int * lp = calloc(n, sizeof(int));
    int * lpp = calloc(n, sizeof(int)); 
    int * z = calloc(n, sizeof(int));
    int * zr = calloc(n, sizeof(int));

    rlist_t ** rs = calloc(256, sizeof(rlist_t *));
    rlist_t * rpool = calloc(n, sizeof(rlist_t));
  
    // We will need the z-values for the forward and reverse pattern 
    int i;
    zbox_linear(p, n, z); 
    zbox_linear(pr, n, zr); 
    for (i=0; i<n; i++)
        lp[i] = 0;

    // Calculate lp values (uses reverse z-values)
    int j;
    for (j=0; j<n; j++)
    {
        i = n - zr[n-j];
        lp[i] = j; 
    }

    // Calculate the lpp values (uses normal z-values)
    lpp[0] = n;
    lpp[n-1] = z[n-1];
    for (i=n-2; i>0; i--)
    {
        if (lpp[i+1] > z[i])
            lpp[i] = lpp[i+1];
        else
            lpp[i] = z[i]; 
    }

    // Calculate the r values for the extended bad character rule
    int ridx = 0;
    for (i=0; i<n; i++)
    {
        // Push an available r node onto this character's list
        rpool[ridx].next = rs[(int)p[i]];
        rpool[ridx].pos = i;
        rs[(int)p[i]] = &rpool[ridx];

        ridx++;
    }

    // Run the matching algorithm
    int k, h, gss, bcs, maxs;
    rlist_t * ri;
    k = n - 1;
    while (k < m)
    {
        i = n - 1;
        h = k;
      
        // Performs backwards search 
        while (i >= 0 && p[i] == t[h])
        {
            i--;
            h--;
        }

        // We have a match!
        if (i < 0)
        {
            int midx = h+1;
            match->proc(midx, (char *)(t + midx), match);
            k += n - lpp[1];
        }
        else  // Perform the maximal pattern shift
        {
            // First comparison is a mismatch
            if (h == k)
                maxs = 1;
            else 
            {
                gss = bcs = 0;
           
                j = i + 1;

                // Obtain the strong good suffix shift (gss)
                if (lp[j] > 0)
                    gss = n - lp[j];
                else
                    gss = n - lpp[j]; 

                
                // Also find the bad character shift (bcs)
                ri = rs[(int)t[h]];
                while (ri && ri->pos >= i)
                    ri = ri->next;

                if (!ri)
                    bcs = i + 1;
                else
                    bcs = i - ri->pos;

                // Choose the maximal shift
                if (gss > bcs)
                    maxs = gss;
                else
                    maxs = bcs;

            }

            // Shift.
            k += maxs;
        }
        
    }
    
    free(pr);
    free(z);
    free(zr);
    free(lp);
    free(lpp);
}
  
int main(int argc, char ** argv) 
{
    // Initialize the strmatch structure
    strmatch_t match = {.num_matches = 0, .proc = proc_match};

    // Two sample strings
    char * p = "abab";
    //char * p = "abcc";
    char * t = "abababcababcccdxabaxabab";

    // Test naive match
    strmatch_naive(p, t, &match);
    printf("Testing the naive match: %u\n", match.num_matches);

    // Test zboxes for a variety of patterns (linear vs. naive as well)
    int n = strlen(p);
    int * z = calloc(n, sizeof(int));
    zbox_naive(p, n, z);
    printz(z, n, p);
    bzero(z, n*sizeof(int));
    zbox_linear(p, n, z);
    printz(z, n, p);    

    char * p2 = "abcd";
    memset(z, '\0', n*sizeof(int));
    zbox_naive(p2, n, z);
    printz(z, n, p2);
    memset(z, '\0', n*sizeof(int));
    zbox_linear(p2, n, z);
    printz(z, n, p2);

    char * p3 = "aaaa";
    memset(z, '\0', n*sizeof(int));
    zbox_naive(p3, n, z);
    printz(z, n, p3);
    memset(z, '\0', n*sizeof(int));
    zbox_linear(p3, n, z);
    printz(z, n, p3);

    free(z);

    // Testing linear match
    match.num_matches = 0;
    strmatch_linear(p, t, &match);
    printf("Testing the linear match: %u\n", match.num_matches);

    // Testing Knuth-Morris-Pratt match
    match.num_matches = 0;
    strmatch_kmp(p, t, &match);
    printf("Testing the KMP match: %u\n", match.num_matches);

    // Testing Boyer-Moore match
    match.num_matches = 0;
    strmatch_bm(p, t, &match);
    printf("Testing the Boyer-Moore match: %u\n", match.num_matches);
    
    return 0;
}