#include using namespace std; string st; char arr[800005]; int lps[800005]; void countPatternLPS(int lenOfPattern){ int i, lenPreffixSuffix = 0; lps[0] = 0; i = 1; while(i < lenOfPattern){ if(arr[i] == arr[lenPreffixSuffix]){ lps[i] = lenPreffixSuffix + 1; i++; lenPreffixSuffix++; }else{ if (lenPreffixSuffix != 0){ lenPreffixSuffix = lps[lenPreffixSuffix - 1]; } else{ lps[i] = 0; i++; } } } } //int KMPSearch(char * pat, char * txt, int * lps, int M, int N){ // int res = 0; // int i=0, currLenPat =0; // while(i < N){ // if(txt[i] == pat[currLenPat]){ // i++; // currLenPat++; // if(currLenPat == M){ // res++; // currLenPat = lps[currLenPat - 1]; // } // } else{ // if(currLenPat == 0){ // i++; // } else{ // currLenPat = lps[currLenPat - 1]; // } // } // } // return res; //} int main() { int strLen; cin>>strLen; cin>>st; arr[strLen] = '#'; for(int i=strLen-1;i>=0;i--){ arr[strLen-1-i] = st[i]; } for(int i=0;i