awsmpshk

Z-function (python)

Oct 6th, 2021 (edited)
293
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. def z_function(s: str) -> list:
  2.     n: int = len(s)
  3.     zf: list = [0 for _ in range(n)]
  4.     for i in range(n):
  5.         while i + zf[i] < n and s[zf[i]] == s[i + zf[i]]:
  6.             zf[i] += 1
  7.            
  8.     return zf
  9.  
  10.  
  11. def effective_z_function(s: str) -> list:
  12.     n: int = len(s)
  13.     left: int = 0
  14.     right: int = 0
  15.     zf: list = [0 for _ in range(n)]
  16.     for i in range(n):
  17.         zf[i] = max(0, min(right - i, zf[i - left]))
  18.         while zf[i] < n and s[zf[i]] == s[i + zf[i]]:
  19.             zf[i] += 1
  20.         if i + zf[i] > right:
  21.             left = i
  22.             right = i + zf[i]
  23.    
  24.     return zf
  25.  
  26. def random_string(count: int) -> str:
  27.     return ''.join(random.choice(string.ascii_letters) for _ in range(count))
RAW Paste Data Copied