FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
interview/python/string/Z_Algorithm.py at master · ankursd/interview · GitHub
ankursd
interview
Repository navigation
Code
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
interview
/
python
/
string
/
Z_Algorithm.py
Copy path
More file actions
More file actions
Latest commit
History
History
History
54 lines (44 loc) · 1.4 KB
Breadcrumbs
interview
/
python
/
string
/
Z_Algorithm.py
Copy path
File metadata and controls
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
)
Back
|
FazBrowse Home
|
New Git URL