//
//  main.cpp
//  ZAlgorithm
//
//  Created by Andu Andu on 30/09/2019.
//  Copyright © 2019 Andu Andu. All rights reserved.
//

#include <iostream>
#include <string>

using namespace std;

void getZarray(string str, int Z[]) {
    int n = str.length();
    int L, R, k;
    L=R=0;
    for(int i=1;i<n;i++) {
        if (i > R) {
            L=R=i;
            while ( R<n && str[R-L] == str[R]) {
                R++;
            }
            Z[i] = R-L;
            R--;
        } else {
            k = i-L;
            if(Z[k] < R-i+1) {
                Z[i] = Z[k];
            } else {
                L = i;
                while ( R<n && str[R-L] == str[R]) {
                    R++;
                }
                Z[i] = R-L;
                R--;
            }
        }
    }
}

void searchFor(string text, string pattern) {
    string concat = pattern + "$" + text;
    int l = concat.length();
    int Z[l];
    getZarray(concat, Z);
    for ( int i=0;i<l;i++) {
        if (Z[i] == pattern.length()) {
            cout<<"pattern at index: "<< i-pattern.length() - 1<<"\n";
        }
    }
}

int main() {
    string text = "ANDUECELMAIANDANDUDINAANANDU";
    string pattern = "ANDU";
    searchFor(text, pattern);
    
    return 0;
}