Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def prefix(s):
- 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
- f = prefix(s)
- k = 0
- 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
- n = int(input())
- s = input()
- rs = s[::-1]
- s = s + s
- print(kmp(rs, s))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement