KMP

 #include <iostream>

#include <string>

using namespace std;

// Function to compute the longest prefix suffix (LPS) array

void Prefix_compute(const string& pattern, int lps[], int m) {

    int length = 0;  // length of the previous longest prefix suffix

    int i = 1;

    lps[0] = 0;  // lps[0] is always 0

    while (i < m) {

        if (pattern[i] == pattern[length]) {

            length++;

            lps[i] = length;

            i++;

        } else {

            if (length != 0) {

                length = lps[length - 1];

            } else {

                lps[i] = 0;

                i++;

            }

        }

    }

}

// Function to perform KMP search

void computeKMP(const string& text, const string& pattern) {

    int n = text.length();

    int m = pattern.length();

    // Create LPS array

    int lps[m];

    Prefix_compute(pattern, lps, m);

    int i = 0;  // index for text

    int j = 0;  // index for pattern

    while (i < n) {

        if (pattern[j] == text[i]) {

            i++;

            j++;

        }

        if (j == m) {

            cout << "Found pattern at index " << i - j << endl;

            j = lps[j - 1];

        } else if (i < n && pattern[j] != text[i]) {

            if (j != 0) {

                j = lps[j - 1];

            } else {

                i++;

            }

        }

    }

}

int main() {

    string text = "ABABDABACDABABCABAB";

    string pattern = "ABABCABAB";

    computeKMP(text, pattern);

    return 0;

}