1 2func kmp(s, sub string) int { 3 bu := make([]int, len(sub)) 4 // abcdabd 5 for i, j := 1, 0; i < len(sub); i++ { 6 for j > 0 && sub[j] != sub[i] { 7 j = bu[j-1] 8 } 9 if sub[j] == sub[i] { 10 j++ 11 } 12 bu[i] = j 13 } 14 for i, j := 0, 0; i < len(s); i++ { 15 for j > 0 && s[i] !