FilesExpand file tree

master

/

naive_string_search.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

40 lines (36 loc) · 1.16 KB

master

/

naive_string_search.py

Copy path

Top

File metadata and controls

• Code
• Blame

40 lines (36 loc) · 1.16 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

"""

https://en.wikipedia.org/wiki/String-searching_algorithm#Na%C3%AFve_string_search

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 naive_pattern_search(s: str, pattern: str) -> list:

"""

>>> naive_pattern_search("ABAAABCDBBABCDDEBCABC", "ABC")

[4, 10, 18]

>>> naive_pattern_search("ABC", "ABAAABCDBBABCDDEBCABC")

[]

>>> naive_pattern_search("", "ABC")

[]

>>> naive_pattern_search("TEST", "TEST")

[0]

>>> naive_pattern_search("ABCDEGFTEST", "TEST")

[7]

"""

pat_len = len(pattern)

position = []

for i in range(len(s) - pat_len + 1):

match_found = True

for j in range(pat_len):

if s[i + j] != pattern[j]:

match_found = False

break

if match_found:

position.append(i)

return position

if __name__ == "__main__":

assert naive_pattern_search("ABCDEFG", "DE") == [3]

print(naive_pattern_search("ABAAABCDBBABCDDEBCABC", "ABC"))