GRD3-T08: String Search

#include <bits/stdc++.h>
using namespace std;

typedef long long lli;

const int N = 1e6;

int idxLPP[N + 1];
char trStr[N + 1], ptStr[N + 1];
int lenTr, lenPt;

int main(){

    scanf("%d %d", &lenTr, &lenPt);
    scanf(" %[^\n]", trStr);
    scanf(" %[^\n]", ptStr);

    idxLPP[0] = 0;
    for(int i = 1; i < lenPt; ++i){
        int idx = idxLPP[i - 1];
        do {
            if(ptStr[idx] == ptStr[i]){
                idxLPP[i] = idxLPP[idx] + 1;
                break;
            }
            idx = idxLPP[idx - 1];
        } while (idx > 0);
    }

    int idxT = 0;
    int idxP = 0;
    while(idxT < lenTr){
        if(trStr[idxT] == ptStr[idxP]){
            ++idxT;
            ++idxP;
            if(idxP == lenPt){
                cout << idxT - idxP << "\n";
                idxP = idxLPP[idxP - 1];
            }
        } else if(idxP == 0){
            ++idxT;
        } else {
            idxP = idxLPP[idxP - 1];
        }
    }

    return 0;
}