def prefix(s): k = 0 v = [0]*len(s) for i in range(1, len(s)): k = v[i-1] while k > 0 and s[k] <> s[i]: k = v[k-1] if s[k] == s[i]: k = k + 1 v[i] = k return v def kmp(s, t): index = -1 k = 0; f = prefix(s) for i in range(len(t)): while k > 0 and s[k] <> t[i]: k = f[k-1] if s[k] == t[i]: k = k + 1 if k == len(s): index = i - len(s) + 1 break return index
Разукрашено на tohtml.com