Knuth Morris Pratt Algorithm

• Time : O(len(str) + len(substr))
• Space : O(len(substr))

using namespace std;

vector<int> PI(string& s) {
    int n = s.length();
    vector<int> pi(n);
    for(int i = 1, j = 0; i < n; i++) {
        while(j > 0 and s[i] != s[j]) j = pi[j - 1];
        if(s[j] == s[i])
            pi[i] = ++j;
    }
    return pi;
}

bool knuthMorrisPrattAlgorithm(string str, string substr) {
    vector<int> pi = PI(substr);
    int n = str.length(), m = substr.length();
    for(int i = 0, j = 0; i < n; i++) {
        while(j > 0 and substr[j] != str[i]) j = pi[j - 1];
        if(str[i] == substr[j]) {
            if(++j == m)
                return true;
        }
    }
    
    return false;
}