Z Algorithm

 1func zalgorithm(s string) []int {
 2	n := len(s)
 3	z := make([]int, n)
 4	z[0] = n
 5	for i, j := 1, 0; i < n; {
 6		for i+j < n && s[j] == s[i+j] {
 7			j++
 8		}
 9		z[i] = j
10		if j == 0 {
11			i++
12			continue
13		}
14		k := 1
15		for ; i+k < n && k+z[k] < j; k++ {
16			z[i+k] = z[k]
17		}
18		i += k
19		j -= k
20	}
21	return z
22}
23