kmp

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

void kmp(const string &pattern, const string &word)
{
    int m = pattern.size();
    vector<int> border(m + 1);
    border[0] = -1;
    for (int i = 0; i < m; ++i)
    {
        border[i + 1] = border[i];
        while (border[i + 1] > -1 and pattern[border[i + 1]] != pattern[i])
        {
            border[i + 1] = border[border[i + 1]];
        }
        border[i + 1]++;
    }

    // cout << "pi/lps table for pattern: "
    //      << pattern << "\n";
    // for (int i : border)
    //     cout << i << " ";

    int n = word.size();
    int seen = 0;
    for (int i = 0; i < n; ++i)
    {
        while (seen > -1 and pattern[seen] != word[i])
        {
            seen = border[seen];
        }
        if (++seen == m)
        {
            cout << "\nfound at: " << (i - m + 1);
            seen = border[m];
        }
    }
    // if (!seen)
    // cout << "\nnot found";
}

int main()
{

    string word = "WELCOME TO THAPAR";
    string pattern = "THAPAR";
    kmp(pattern, word);

    return 0;
}