string.cpp

#include <iostream>
#include <string>
#include <vector>


using namespace std;

// KMP Failure Function
vector<int> getPi(string p) {
  int m = p.size(), j = 0;
  vector<int> pi(m, 0);
  for (int i = 1; i < m; i++) {
    while (j > 0 && p[i] != p[j])
      j = pi[j - 1];
    if (p[i] == p[j])
      pi[i] = ++j;
  }
  return pi;
}

// KMP Search
vector<int> kmp(string s, string p) {
  vector<int> ans;
  auto pi = getPi(p);
  int n = s.size(), m = p.size(), j = 0;
  for (int i = 0; i < n; i++) {
    while (j > 0 && s[i] != p[j])
      j = pi[j - 1];
    if (s[i] == p[j]) {
      if (j == m - 1) {
        ans.push_back(i - m + 1);
        j = pi[j];
      } else
        j++;
    }
  }
  return ans;
}

// Trie Node
struct TrieNode {
  TrieNode *children[26];
  bool isEnd;

  TrieNode() {
    for (int i = 0; i < 26; i++)
      children[i] = nullptr;
    isEnd = false;
  }

  ~TrieNode() {
    for (int i = 0; i < 26; i++)
      if (children[i])
        delete children[i];
  }
};

// Trie Insert/Search
void insert(TrieNode *root, string key) {
  TrieNode *curr = root;
  for (char c : key) {
    int idx = c - 'a';
    if (!curr->children[idx])
      curr->children[idx] = new TrieNode();
    curr = curr->children[idx];
  }
  curr->isEnd = true;
}

bool search(TrieNode *root, string key) {
  TrieNode *curr = root;
  for (char c : key) {
    int idx = c - 'a';
    if (!curr->children[idx])
      return false;
    curr = curr->children[idx];
  }
  return curr != nullptr && curr->isEnd;
}