KMP

void kmp(string str){vector<int>ptr;ptr.resize(str.length());//slow ptrint j=0;//fast ptrfor(int i=1;i<str.length();i++){if(s[i]==s[j]){ptr[i]=++j;}else if(j-1>=0){j=ptr[j-1];i–;}}cout<<str.substr(0,j);}
  1. Have a fast pointer and slow pointer ( is the faster one that starts from 1 — we need to compare with at least one previous element) and j starts from 0
  2. The ptr array stores the index in the string after (ie. +1 to its corresponding match to retry the matches .
  3. when there is a match ptr(fast pointer) = next index after the slow pointer match
  4. when there is a mismatch reset the slow pointer to ptr[prev slow ptr pos (because that would have been a match or the first pointer itself] ie j=ptr[j-1] . Reset the fast pointer for retrying

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store