Advertisement
Epillion

Assignment - 1 - Z algorithm - Version 1.0

Mar 26th, 2023
813
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 4.51 KB | None | 0 0
  1. # -*- coding: utf-8 -*-
  2. """
  3. Created on Mon Mar 20 15:56:04 2023
  4.  
  5. @author: ahsan
  6. """
  7.  
  8. def getZarr(string, z):
  9.     n = len(string)
  10.  
  11.     # [L,R] make a window which matches
  12.     # with prefix of s
  13.     l, r, k = 0, 0, 0
  14.     for i in range(1, n):
  15.  
  16.         # if i>R nothing matches so we will calculate.
  17.         # Z[i] using naive way.
  18.         if i > r:
  19.             l, r = i, i
  20.  
  21.             # R-L = 0 in starting, so it will start
  22.             # checking from 0'th index. For example,
  23.             # for "ababab" and i = 1, the value of R
  24.             # remains 0 and Z[i] becomes 0. For string
  25.             # "aaaaaa" and i = 1, Z[i] and R become 5
  26.             while r < n and string[r - l] == string[r]:
  27.                 r += 1
  28.             z[i] = r - l
  29.             r -= 1
  30.         else:
  31.  
  32.             # k = i-L so k corresponds to number which
  33.             # matches in [L,R] interval.
  34.             k = i - l
  35.  
  36.             # if Z[k] is less than remaining interval
  37.             # then Z[i] will be equal to Z[k].
  38.             # For example, str = "ababab", i = 3, R = 5
  39.             # and L = 2
  40.             if z[k] < r - i + 1:
  41.                 z[i] = z[k]
  42.  
  43.             # For example str = "aaaaaa" and i = 2,
  44.             # R is 5, L is 0
  45.             else:
  46.  
  47.                 # else start from R and check manually
  48.                 l = i
  49.                 while r < n and string[r - l] == string[r]:
  50.                     r += 1
  51.                 z[i] = r - l
  52.                 r -= 1
  53.  
  54. def checkTransposition(text, pattern, zvalues, i):
  55.    
  56.     size = len(pattern)
  57.     startIndex = i
  58.     now = 0
  59.     count = 0;
  60.     first, second = -1, -1
  61.    
  62.     while now < size and startIndex < len(text):
  63.         mn = min(zvalues[startIndex], zvalues[now])
  64.        
  65.         now += mn
  66.         startIndex += mn
  67.        
  68.         if now >= size:
  69.             break
  70.        
  71.         count += 1
  72.        
  73.         #print(now, startIndex, mn, count)
  74.         if count > 2:
  75.             break
  76.         if count == 1:
  77.             first = startIndex
  78.         if count == 2:
  79.             second = startIndex
  80.         now += 1
  81.         startIndex += 1
  82.        
  83.         if startIndex >= len(text):
  84.             break
  85.        
  86.         #print("second", now, startIndex, mn, count)
  87.        
  88.         if  zvalues[now] > zvalues[startIndex]:
  89.             continue
  90.        
  91.    
  92.        
  93.         while now < size and zvalues[now] == 0 and text[startIndex] == pattern[now]:
  94.             now += 1
  95.             startIndex += 1
  96.            
  97.         #print("second", now, startIndex, mn, count)    
  98.         if startIndex < len(text) and  zvalues[now] <= zvalues[startIndex] and now + zvalues[now] == size-1:
  99.             break
  100.            
  101.        
  102.    
  103.     #print(i, count, first, second)
  104.     if count == 2:
  105.         if text[first] == text[second-i] and text[second] == text[first-i]:
  106.             print("answer", i, i-size, first-size, second-size)    
  107.         else:
  108.             print("false", i, i-size, first-size, second-size)
  109.     else:
  110.         print(i, i-size,"false")
  111.  
  112.     print("=============")
  113.     return False
  114.  
  115. # prints all occurrences of pattern
  116. # in text using Z algo
  117. def search(text, pattern):
  118.  
  119.     # Create concatenated string "P$T"
  120.     concat = pattern + "$" + text
  121.     l = len(concat)
  122.  
  123.     # Construct Z array
  124.     z = [0] * l
  125.     getZarr(concat, z)
  126.     print(z)
  127.     # now looping through Z array for matching condition
  128.     for i in range(l):
  129.  
  130.         # if Z[i] (matched region) is equal to pattern
  131.         # length we got the pattern
  132.         if z[i] == len(pattern):
  133.             print("Pattern found at index",
  134.                       i - len(pattern))
  135.             print("=============")
  136.         elif i < l - len(pattern) + 1:
  137.             checkTransposition(concat, pattern, z, i)
  138.            
  139.            
  140.  
  141.  
  142. search('babbababaabbaba','abba')
  143.  
  144.  
  145. # Pattern found at index 2
  146. # =============
  147. # 7 3 false
  148. # =============
  149. # answer 8 4 4 5
  150. # =============
  151. # 9 5 false
  152. # =============
  153. # answer 10 6 6 7
  154. # =============
  155. # false 11 7 7 9
  156. # =============
  157. # 12 8 false
  158. # =============
  159. # 13 9 false
  160. # =============
  161. # Pattern found at index 10
  162. # =============
  163. # 15 11 false
  164. # =============
  165. # answer 16 12 12 13
  166. # =============
  167.  
  168. # aabc$aaabdaac
  169. # 0100023100210
  170.  
  171. #babbababaabbaba
  172. #abba
  173.  
  174.  
  175. #abbac...$babbababaabbaba
  176. #00010040020201400201
  177.  
  178. #abbabba
  179. #babab
  180. #abbac
  181. #ac
  182. #1
  183. #ab
  184. #2
  185. # transposition 1
  186. # abbb
  187. # bbbb
  188.  
  189. # wholetext = text + pattern, pattern, zvalues, i
  190.  
  191. #aba
  192. #abba
  193.  
  194.  
  195.  
  196.  
  197.  
  198.  
  199.  
  200.  
  201.  
  202.  
  203.  
  204.  
  205.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement