#include <iostream>

using namespace std;
string text;

int * LPS(const string & subStr) {
    int n = subStr.size();
    int * lps = new int[n];

    int j = 0;
    lps[0] = 0;

    int i = 1;
    while(i < n) {
        if(subStr[i] == subStr[j]) {
            j++;
            lps[i] = j;
            i++;
        }
        else {
            if(j == 0) {
                lps[i] = 0;
                i++;
            }
            else {
                j = lps[j - 1];
            }
        }
    }

    return lps;
}
int * reverseLPS(const string & subStr) {
    int m = subStr.size();
    int * lps = new int[m];
    int len = 0;
        int i = m - 2;

        while (i >= 0) {
            if (subStr[i] == subStr[m - 1 - len]) {
                len++;
                lps[i] = len;
                i--;
            } else {
                if (len != 0) {
                    len = lps[m - len];
                } else {
                    lps[i] = 0;
                    i--;
                }
            }
        }
    for(int i = 0; i < m; i++) {
        cout << lps[i] << " ";
    }
    return lps;
}
int* findAllSubStr(const string & subStr) {
    int * lps = LPS(subStr);
    int n = subStr.size();
    int * res = new int[n];
    int r = 0;

    int i = 0, j = 0;
    while(i < (int) text.size()) {
        if(text[i] == subStr[j]) {
            i++;
            j++;

            if(j == n) {
                res[r++] = i - j;
                cout << i - j << endl;
                j = lps[j - 1];
            }
        }
        else {
            if(j != 0) {
                j = lps[j - 1];
            }
            else {
                i++;
            }
        }
    }

    int *res_array = new int[r];
    for(int i = 0; i < r; i++) {
        res_array[i] = res[i];
    }

    return res_array;
}
int findFirstSubStr(const string & subStr) {
    int * lps = LPS(subStr);
    int n = subStr.size();

    int i = 0, j = 0;
    while(i < (int) text.size()) {
        if(text[i] == subStr[j]) {
            i++;
            j++;

            if(j == n) {
                return i - j;
            }
        }
        else {
            if(j != 0) {
                j = lps[j - 1];
            }
            else {
                i++;
            }
        }
    }
    return -1;
}
int findLastSubStr(const string & subStr) {
    int * lps = reverseLPS(subStr);
    int m = subStr.size();

    int i = text.size() - 1, j = m - 1;
    while(i >= 0) {
        if(text[i] == subStr[j]) {
            i--;
            j--;

        }
        if(j < 0) {
            return i + 1;
        }
        else if(i >= 0 and text[i] != subStr[j]) {
            if(j != m - 1) {
                j = m - 1 - lps[j];
            }
            else {
                i--;
            }
        }
    }
    return -1;
}
int * findAllSubStrReverse(const string & subStr) {
    int * lps = reverseLPS(subStr);
    int m = subStr.size();
    int * res = new int [m];
    int i = text.size() - 1, j = m - 1;
    int last_pos = -1;
    int r = 0;
    while(i >= 0) {
        if(text[i] == subStr[j]) {
            i--;
            j--;

        }
        if(j < 0) {
            j = m - 1 - lps[j + 1];
            res[r++] = i + 1;
        }
        else if(i >= 0 and text[i] != subStr[j]) {
            if(j != m - 1) {
                j = m - 1 - lps[j];
            }
            else {
                i--;
            }
        }
    }
    return res;
}
int main() {
    text = "ababxabababaxababa";
    string pat = "ababa";
    findAllSubStr(pat);
    return 0;
}