#include <stdio.h>
#include "kmppat.h"

TextPattern::TextPattern(char *pat) {
    pat_len = strlen(pat);
    pattern = new char[pat_len];
    for(int i = 0; i < pat_len; i++) pattern[i] = pat[i];

    next = new int[pat_len];
    next[0] = -1;

    int j = -1;
    int k = 0;
    while(k < pat_len - 1) {
        while(j >= 0 && pat[k] != pat[j]) j = next[j];
        j++;
        k++;
        next[k] = (pat[k] == pat[j] ? next[j] : j);
    }
}

TextPattern::~TextPattern() {
    delete[] pattern;
    delete[] next;
}

int
TextPattern::firstMatch(char *text) {
    int j = 0;
    int k = 0;
    while(text[k]) {
        while(j >= 0 && text[k] != pattern[j]) j = next[j];
        k++;
        j++;
        if(j == pat_len) return k - pat_len;
    }
    return -1;
}