int n = s.length();
int[] p = new int[n + 1];
p[0] = -1;
for (int i = 0; i < n; i++) {
	int k = p[i];
	char c = s.charAt(i);
	while ((k >= 0) && (s.charAt(k) != c)) {
		k = p[k];
	}
	p[i + 1] = k + 1;
}

p = [-1]
k = -1
for c in s:
	while k >= 0 and s[k] != c:
		k = p[k]
	k += 1
	p.append(k)