#include <malloc.h>
#include <string.h>

#define CHUNK 5

int create_lps(char *pattern, int pattern_len, int *lps) {
    int last_matched_char = 1;
    int last_prefix_char = 0;

    lps[0] = 0;

    while (last_matched_char < pattern_len) {
        if (pattern[last_matched_char] == pattern[last_prefix_char]) {
            lps[last_matched_char] = last_prefix_char + 1;
            last_matched_char++;
            last_prefix_char++;
        } else if (last_prefix_char != 0)
            // check if matches the previous prefix
            last_prefix_char = lps[last_prefix_char - 1];
        else {
            // if there isn't a prefix restart from the begin
            lps[last_matched_char] = 0;
            last_matched_char++;
        }
    }
}

int *search_pattern(char *text, char *pattern, int *lps, int *match_number, int *residue) {
    int size = CHUNK;
    int *matches = (int *) malloc(sizeof(int) * size);
    int text_index = 0;
    int pattern_index = 0;
    int text_len = strlen(text);
    int pattern_len = strlen(pattern);

    while (text_index < text_len) {
        // char matches
        if (text[text_index] == pattern[pattern_index]) {
            text_index++;
            pattern_index++;

            // full match found
            if (pattern_index == pattern_len) {

                // growth array if full
                if (*match_number == size) {
                    size *= 2;
                    matches = (int *) realloc(matches, size * sizeof(int));
                }

                matches[*match_number] = text_index - pattern_len;
                *match_number = *match_number + 1;
                pattern_index = lps[pattern_index - 1];
            }
            // char not matches on first char
        } else if (pattern_index == 0) {
            text_index++;
        } else {
            pattern_index = lps[pattern_index - 1];
        }
    }

    *residue = pattern_index;
    return matches;
}