KMP

The idea is to basically use an extra array to store the index after the corresponding match index for retying in case of mismatch

Complexity : O(m+n)

void kmp(string str)
{
vector<int>ptr;
ptr.resize(str.length());
//slow ptr
int j=0;
//fast ptr
for(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);
}

Explanation:

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