FilesExpand file tree

 master

/

Z_Algorithm.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

54 lines (44 loc) · 1.4 KB

 master

/

Z_Algorithm.py

Copy path

Top

File metadata and controls

• Code
• Blame

54 lines (44 loc) · 1.4 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

#author: Pankaj Kumar

#time complexity: O(length(string) + length(pattern))

#space complexity: O(length(string) + length(pattern))

#Link to theory: http://www.geeksforgeeks.org/z-algorithm-linear-time-pattern-searching-algorithm/

def z_algo(arr):

z = [0 for i in range(len(arr))]

left , right = 0 , 0

for k in range(1 , len(arr)):

if k > right:

left = k

right = k

while right < len(arr) and arr[right] == arr[right-left]:

right += 1

z[k] = right - left

right -= 1

else:

k1 = k - left

if z[k1] < right - k + 1:

z[k] = z[k1]

else:

left = k

while right < len(arr) and arr[right] == arr[right-left]:

right += 1

z[k] = right - left

right -= 1

return z

def makepattern(string , pattern):

n , m = len(string) , len(pattern)

str_arr = []

for i in range(m):

str_arr.append(pattern[i])

str_arr.append('$')

for i in range(n):

str_arr.append(string[i])

z_values = z_algo(str_arr)

result = []

for i in range(len(z_values)):

if z_values[i] == m:

result.append(i - m - 1)

print result

if __name__ == '__main__':

string = 'abcdeabcd'

pattern = 'abc'

makepattern(string , pattern)