西窗月

Understanding KMP

Useful links for understanding.

  • Understand how kmp works, Post by Ruanyi Feng

  • Understand how to calculate the next table, post from Zhihu

My implementation of calculate next table.

1
2
3
4
5
6
7
8
9
10
11
vector<int> cal_next(string s) {
vector<int> next(s.size(), 0);

int j = 0; // keep track of the pointer it should match
for (int i = 1; i < s.size(); ++i) {
while (j > 0 && s[i] != s[j]) j = next[j-1];
if (s[i] == s[j]) { j++; }
next[i] = j;
}
return next;
}