///KMP pattern searching in a string
///6-Apr-2020

#include <iostream>

int main() {
    char text[] = "abazaababaababababc";
    char pattern[] = "ababc";
    int pat_len = strlen(pattern);
    int txt_len = strlen(text);
    int i, j=0;
    int fail_vector[5];

/// Computing the fail_function
/// fail function will have under the letter the longest suffix that is also a preffix of the current substring
///for example fail_vector[ababc]={-1,0,1,2,0}
        int max_suf = 0;
        fail_vector[0] = -1;
        i = 1;
        while (i < pat_len) {
            if (pattern[i] == pattern[max_suf]) {
                max_suf++;
                fail_vector[i] = max_suf;
                i++;
            }
            else
            {
                if (max_suf != 0) {
                    max_suf = fail_vector[max_suf - 1];
                    fail_vector[i] = 0;
                }
                else
                {
                    fail_vector[i] = 0;
                    i++;
                }
            }
        }
///end of fail_function

///KMP search
    i = j = 0;
    while (i < txt_len) {
        if (pattern[j] = text[i]) {
            j++;
            i++;
        }
        if (j == pat_len) {
            std::cout << "First pattern found at index  "  << i - j;
            j = fail_vector[j - 1];
            return 0;
        }
        else if (i < txt_len && pattern[j] != text[i]) {
            if (j != 0)
                j = fail_vector[j - 1];
            else
                i++;
        }
    }
///end of KMP search
    return 0;
}