Knuth-Morris-Pratt Algorithm

[annw3y]

I found some code ahout knuth-morris-pratt algorithm , but i don't know what it means, can somenone please tell me what this code does, how it works.

int kmp(const string &T, const string &P) {
if (P.empty())
return 0;
else{


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;
}
}

[MikeStgt]

I found some code ahout knuth-morris-pratt algorithm

1. Where did you find it?
2. Did you look elsewhere? For example: https://de.wikipedia.org/wiki/Knuth-Morris-Pratt-Algorithmus (the french and english versions are not so colourful).

[ne555]

lástima que soy daltónico

[Duthomhas]

The English version is also colorful, just not in a fancy table.

It suffers from the same color design problem, though: differing colors are equally saturated, making it hard for colorblind people to tell them apart.

Maybe someone wants to fix it?
Or at least comment about color issues on the meta?