Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # -*- coding: utf-8 -*-
- """
- Created on Mon Mar 20 15:56:04 2023
- @author: ahsan
- """
- def getZarr(string, z):
- n = len(string)
- # [L,R] make a window which matches
- # with prefix of s
- l, r, k = 0, 0, 0
- for i in range(1, n):
- # if i>R nothing matches so we will calculate.
- # Z[i] using naive way.
- if i > r:
- l, r = i, i
- # R-L = 0 in starting, so it will start
- # checking from 0'th index. For example,
- # for "ababab" and i = 1, the value of R
- # remains 0 and Z[i] becomes 0. For string
- # "aaaaaa" and i = 1, Z[i] and R become 5
- while r < n and string[r - l] == string[r]:
- r += 1
- z[i] = r - l
- r -= 1
- else:
- # k = i-L so k corresponds to number which
- # matches in [L,R] interval.
- k = i - l
- # if Z[k] is less than remaining interval
- # then Z[i] will be equal to Z[k].
- # For example, str = "ababab", i = 3, R = 5
- # and L = 2
- if z[k] < r - i + 1:
- z[i] = z[k]
- # For example str = "aaaaaa" and i = 2,
- # R is 5, L is 0
- else:
- # else start from R and check manually
- l = i
- while r < n and string[r - l] == string[r]:
- r += 1
- z[i] = r - l
- r -= 1
- def checkTransposition(text, pattern, zvalues, i):
- size = len(pattern)
- startIndex = i
- now = 0
- count = 0;
- first, second = -1, -1
- while now < size and startIndex < len(text):
- mn = min(zvalues[startIndex], zvalues[now])
- now += mn
- startIndex += mn
- if now >= size:
- break
- count += 1
- #print(now, startIndex, mn, count)
- if count > 2:
- break
- if count == 1:
- first = startIndex
- if count == 2:
- second = startIndex
- now += 1
- startIndex += 1
- if startIndex >= len(text):
- break
- #print("second", now, startIndex, mn, count)
- if zvalues[now] > zvalues[startIndex]:
- continue
- while now < size and zvalues[now] == 0 and text[startIndex] == pattern[now]:
- now += 1
- startIndex += 1
- #print("second", now, startIndex, mn, count)
- if startIndex < len(text) and zvalues[now] <= zvalues[startIndex] and now + zvalues[now] == size-1:
- break
- #print(i, count, first, second)
- if count == 2:
- if text[first] == text[second-i] and text[second] == text[first-i]:
- print("answer", i, i-size, first-size, second-size)
- else:
- print("false", i, i-size, first-size, second-size)
- else:
- print(i, i-size,"false")
- print("=============")
- return False
- # prints all occurrences of pattern
- # in text using Z algo
- def search(text, pattern):
- # Create concatenated string "P$T"
- concat = pattern + "$" + text
- l = len(concat)
- # Construct Z array
- z = [0] * l
- getZarr(concat, z)
- print(z)
- # now looping through Z array for matching condition
- for i in range(l):
- # if Z[i] (matched region) is equal to pattern
- # length we got the pattern
- if z[i] == len(pattern):
- print("Pattern found at index",
- i - len(pattern))
- print("=============")
- elif i < l - len(pattern) + 1:
- checkTransposition(concat, pattern, z, i)
- search('babbababaabbaba','abba')
- # Pattern found at index 2
- # =============
- # 7 3 false
- # =============
- # answer 8 4 4 5
- # =============
- # 9 5 false
- # =============
- # answer 10 6 6 7
- # =============
- # false 11 7 7 9
- # =============
- # 12 8 false
- # =============
- # 13 9 false
- # =============
- # Pattern found at index 10
- # =============
- # 15 11 false
- # =============
- # answer 16 12 12 13
- # =============
- # aabc$aaabdaac
- # 0100023100210
- #babbababaabbaba
- #abba
- #abbac...$babbababaabbaba
- #00010040020201400201
- #abbabba
- #babab
- #abbac
- #ac
- #1
- #ab
- #2
- # transposition 1
- # abbb
- # bbbb
- # wholetext = text + pattern, pattern, zvalues, i
- #aba
- #abba
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement