Advertisement
1nikitas

Untitled

Oct 17th, 2019
381
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.59 KB | None | 0 0
  1.  
  2. def prefix(s):
  3.     v = [0]*len(s)
  4.     for i in range(1,len(s)):
  5.         k = v[i-1]
  6.         while k > 0 and s[k] != s[i]:
  7.             k = v[k-1]
  8.         if s[k] == s[i]:
  9.             k = k + 1
  10.         v[i] = k
  11.     return v
  12. def kmp(s,t):
  13.     index = -1
  14.     f = prefix(s)
  15.     k = 0
  16.     for i in range(len(t)):
  17.         while k > 0 and s[k] != t[i]:
  18.             k = f[k-1]
  19.         if s[k] == t[i]:
  20.             k = k + 1
  21.         if k == len(s):
  22.             index = i - len(s) + 1
  23.             break
  24.     return index
  25. n = int(input())
  26. s = input()
  27. rs = s[::-1]
  28. s = s + s
  29. print(kmp(rs, s))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement