#include <iostream>
#include <sstream>
#include <fstream>
#include<stdio.h>
#include<string.h>
#define NO_OF_CHARS 256
using namespace std;

void naive_search(string pat, string txt)
{
    int M = pat.length();
    int N = txt.length();

    /* A loop to slide pat[] one by one */
    for (int i = 0; i <= N - M; i++)
    {
        int j;

        /* For current index i, check for pattern match */
        for (j = 0; j < M; j++)
        {
            if (txt[i + j] != pat[j])
                break;
        }
        if (j == M) // if pat[0...M-1] = txt[i, i+1, ...i+M-1]
        {
            printf("Pattern found at index %d n", i);
        }
    }
}
int goNextState(string pattern, int num_total_state, int state, int given_character) {

    // If our character match with the pattern

    if (state < num_total_state && given_character == pattern[state])
        return state + 1;

    int nextstate, index;

    //If dont match, search the maximum legth of matched pattern
    // For example pattern is = aabb and our index is aabc , start to match first character of pattern and last character of given index increasingly and decreasingly..

    for (nextstate = state; nextstate > 0; nextstate--)
    {
        if (pattern[nextstate - 1] == given_character) // start to find longest matched substring
        {
            for (index = 0; index < nextstate - 1; index++) {
                if (pattern[index] != pattern[state - nextstate + 1 + index])
                    break;
            }
            if (index == nextstate - 1)
                return  nextstate;
        }
    }
    return 0;
}

void Transition_Table(string pattern, int lengt_of_pattern, int  Table_Array[][NO_OF_CHARS])

{

    int given_character;
    int state;

    for (state = 0; state <= lengt_of_pattern; state++)
        for (given_character = 0; given_character<NO_OF_CHARS; ++given_character)

            Table_Array[state][given_character] = goNextState(pattern, lengt_of_pattern, state, given_character);
}

void Automata_Compute(string pattern, string given_text) {
    int numberOfLine = 0;

    int count = 0;
    int A = pattern.length();
    int B = given_text.length();

    int Table_Array[50][NO_OF_CHARS];

    Transition_Table(pattern, A, Table_Array);

    int i, state = 0;
    for (i = 0; i<B; i++) {

        // get input ...
        istringstream stream(given_text);
        string line;
        for (int a = 0; getline(stream, line); ++a) {

            state = Table_Array[state][given_text[i]];

            if (state == A) {
                count++;
                printf("n pattern found at line %d , %d", a, count);
            }
        }
    }
}

// Driver program to test above function
int main()
{

   /*ifstream file("stringExample");
    string content((istreambuf_iterator<char>(file)),
    (istreambuf_iterator<char>()));*/

   ifstream ifile("stringExample.txt"); // open
   string str(istreambuf_iterator<char>(ifile), {});

string pat = ("AABA");
string text = (str);

    naive_search(pat, text);

    Automata_Compute(pat, text);

    return 0;
}