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

int *
kmp_prefix(const char *needle, int nsize)
{
    int i = 1;
    int k = -1;
    int *pi = malloc(sizeof(int) * nsize);

    pi[0] = k;
    for (i = 1; i < nsize; i++) {
        while (k > -1 && needle[k + 1] != needle[i])
            k = pi[k];
        if (needle[i] == needle[k + 1])
            k++;
        pi[i] = k;
    }
    return pi;
}

char *
kmp_strstr(const char *haystack, const char *needle)
{
    int i, k = -1;
    int nsize = strlen(needle);
    int hsize = strlen(haystack);
    int *pi = kmp_prefix(needle, nsize);

    for (i = 0; i < hsize; i++) {
        while (k > -1 && needle[k + 1] != haystack[i])
            k = pi[k];
        if (haystack[i] == needle[k + 1])
            k++;
        if (k == nsize - 1) {
            free(pi);
            return (char*) haystack + i - k;
        }
    }
    free(pi);
    return NULL;
}

char *
naive_strstr(const char *haystack, const char *needle)
{
    int i, j;
    int nsize = strlen(needle);
    int hsize = strlen(haystack);
    for (i = 0; i < hsize - nsize + 1; i++) {
        for (j = 0; j < nsize; j++)
            if (haystack[i + j] != needle[j])
                break;
        if (j == nsize)
            return (char*) haystack + i;
    }
    return NULL;
}

int
main(int argc, char *argv[])
{
    const int nsize = 32 * 1024;
    const int hsize = 32 * 1024 * 1024;

    int i;
    char *needle = malloc(nsize);
    char *haystack = malloc(hsize);

    for (i = 0; i < nsize - 1; i++)
        needle[i] = 'a';
    for (i = 0; i < hsize - 1; i++)
        haystack[i] = 'a';

    needle[nsize - 1] = 0;
    needle[nsize / 2] = 'b';
    haystack[hsize - 1] = 0;

    if (argc < 2)
        return 1;
    else if (!strcmp(argv[1], "kmp"))
        return !!kmp_strstr(haystack, needle);
    else if (!strcmp(argv[1], "naive"))
        return !!naive_strstr(haystack, needle);
    // else if (!strcmp(argv[1], "tsar"))
    //    return !!tsar_strstr(haystack, needle);
}