forked from TheAlgorithms/Python
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathnaive_string_search.py
More file actions
32 lines (27 loc) · 837 Bytes
/
naive_string_search.py
File metadata and controls
32 lines (27 loc) · 837 Bytes
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
"""
this algorithm tries to find the pattern from every position of
the mainString if pattern is found from position i it add it to
the answer and does the same for position i+1
Complexity : O(n*m)
n=length of main string
m=length of pattern string
"""
def naivePatternSearch(mainString, pattern):
patLen = len(pattern)
strLen = len(mainString)
position = []
for i in range(strLen - patLen + 1):
match_found = True
for j in range(patLen):
if mainString[i + j] != pattern[j]:
match_found = False
break
if match_found:
position.append(i)
return position
mainString = "ABAAABCDBBABCDDEBCABC"
pattern = "ABC"
position = naivePatternSearch(mainString, pattern)
print("Pattern found in position ")
for x in position:
print(x)