#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 n = subStr.size();
    int * lps = new int[n];
    
    int j = 0;
//    lps[0] = 0;
//    
    for(int i = n - 2; i >= 0; i--) {
        while(j > 0 and subStr[i] != subStr[n - j - 1]) {
            j = lps[n - j];
        }
        if(subStr[i] == subStr[n - j - 1]) {
            j++;
        }
        lps[i] = j;
    }
    for(int i = 0; i < n; 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 n = subStr.size();
    
    int i = text.size() - 1, j = n - 1;
    while(i >= 0) {
        if(text[i] == subStr[j]) {
            i--;
            j--;
            
            if(j == 0) {
                return i;
            }
        }
        else {
            if(j != n - 1) {
                j = lps[n - j - 1];
            }
            else {
                i--;
            }
        }
    }
    return -1;
}
int main() {
    text = "ABABABCABABC";
    string pat = "abcabcy";
    int p = findLastSubStr(pat);
    return 0;
}