boyermoore

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

void search(string word, string pattern)
{
    const int n = word.size();
    const int m = pattern.size();

    vector<int> badMatch(52, -1);
    for (int i = 0; i < m; i++)
        badMatch[pattern[i] - 'a'] = i;

    int shift = 0;
    while (shift <= (n - m))
    {
        int j = m - 1;

        while (j >= 0 && pattern[j] == word[shift + j])
            j--;

        if (j < 0)
        {
            cout << "\nfound at: " << shift << endl;
            shift += (shift + m < n) ? m - badMatch[word[shift + m]] : 1;
        }

        else
            shift += max(1, j - badMatch[word[shift + j]]);
    }
}

int main()
{
    string word = "WELCOME TO THAPAR";
    string pattern = "THAPAR";
    search(word, pattern);
    return 0;
}