Prefix function. KMP algorithm - YessineJallouli/Competitive-Programming GitHub Wiki

string ch,s; cin >> ch >> s;
int n = s.size();
/// Prefix function
vector<int> pr(n);
pr[0] = 0;
for (int i = 1; i < n; i++) {
   int j = pr[i-1];
   while (j > 0 && s[j] != s[i])
      j = pr[j-1];
   if (s[i] == s[j])
      j++;
   pr[i] = j;
}
/// Pattern matching
bool ans = false;
int j = 0;
for (int i = 0; i < (int) ch.size(); i++) {
   while (j > 0 && ch[i] != s[j])
      j = pr[j-1];
   if (ch[i] == s[j])
      j++;
   if (j == n)
      ans = true;
}