Theory

• Knuth–Morris–Pratt algorithm
• Knuth-Morris-Pratt substring search

Implementation

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

class KMP {
private:
    static int const R = 256; // The radix
    vector<vector<int>> dfa;
    string pattern;
public:
    KMP(string pattern) {
        this->pattern = pattern;
        // Compute DFA
        dfa = vector<vector<int>>(R, vector<int>(pattern.size() + 1));

        // The first character in the pattern transitions to state 1
        dfa[pattern[0]][0] = 1;

        int x = 0; // Restart state
        int m = pattern.size();
        for (int j = 1; j < m; j++) {
            for (int i = 0; i < R; i++) {
                dfa[i][j] = dfa[i][x];          // Copy mismatch cases
            }
            dfa[pattern[j]][j] = j + 1;         // Set match case
            x = dfa[pattern[j]][x];             // Update restart state
        }
    }

    int search(string text) {
        int n = text.size();
        int m = pattern.size();
        int j = 0, i;
        for (i = 0; i < n; i++) {
            j = dfa[text[i]][j];
            if (j == m) { return i - m + 1; }

        }
        return -1;
    }
};

Practice problems

• https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string