Skip to content

Instantly share code, notes, and snippets.

@gongzhitaao
Last active January 4, 2022 08:07
Show Gist options
  • Save gongzhitaao/5e9d8f80aaba60e14a2c to your computer and use it in GitHub Desktop.
Save gongzhitaao/5e9d8f80aaba60e14a2c to your computer and use it in GitHub Desktop.
KMP implementation in C++
int kmp(const string &T, const string &P) {
if (P.empty()) return 0;
vector<int> pi(P.size(), 0);
for (int i = 1, k = 0; i < P.size(); ++i) {
while (k && P[k] != P[i]) k = pi[k - 1];
if (P[k] == P[i]) ++k;
pi[i] = k;
}
for (int i = 0, k = 0; i < T.size(); ++i) {
while (k && P[k] != T[i]) k = pi[k - 1];
if (P[k] == T[i]) ++k;
if (k == P.size()) return i - k + 1;
}
return -1;
}
@BoshenGuan
Copy link

mix-using of int and size_t potentially introduces problems.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment