Python: Bruteforce, BoyreMoore Matching Algorithm
2020. 2. 19. 13:14ㆍ2020/Algorithm
|
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
|
# _*_ coding=utf-8 _*_
#BruteForce String matching Algorithm
def bruteforce( pattern, text ):
lengthOfPattern = len(pattern)
lengthOfText = len(text)
i = 0
while i <= lengthOfText - lengthOfPattern:
j = 0
while j < lengthOfPattern:
if text[i+j] != pattern[j]:
break
j = j + 1
if j == lengthOfPattern:
return 1
i = i + 1
return 0
#str_1 = input()
#str_2 = input()
#res = bruteforce( str_1, str_2)
########## BoyreMoore ###############
# 찾는 문자열의 요소에 따라 스킵할 칸 수를 조정한다.
# 문자열에서 패턴과 일치하지 않는 문자열을 발견한 경우 해당 문자에 따라서
# 이동할 칸수를 결정하기 위해 테이블을 생성한다. (파이썬의 경우 딕셔너리 활용)
def makebmt(pattern):
lengthOfPattern = len(pattern)
mydict = {}
for x in range(len(pattern)):
index = pattern[x]
# 무조건 옆으로 한 칸 이동해야하기 떄문에 1보다 작아서는 안된다
value = max(1,lengthOfPattern-1-x)
mydict[index] = value
return mydict
# pattern= 'test' => mydict = { 'e':2, 's':1, 't':1 } (중복문자는초기화됨)
def boymoreMatching(pattern, mydict, text):
lengthOfPattern = len(pattern)
lengthOfText = len(text)
mydict = mydict
i = 0
while i <= lengthOfText - lengthOfPattern: # 검색할 문자 시작점 지정
numOfSkip = 0
j = lengthOfPattern-1 #패턴의 뒤부터 검색
while j >= 0:
if text[i+j] != pattern[j]: # 패턴이 일치하지 않는 경우
if text[i+j] in mydict.keys(): # 문자열의 문자가 딕셔너리에 있는지 확인
numOfSkip = mydict[ text[i+j] ]
break
else: # 딕셔너리에 해당 문자 없음 -> 비교할 가치 없음
numOfSkip = len(pattern) # 따라서 문자길이만큼 이동
break
j = j - 1
if numOfSkip == 0: # 패턴의 모든 값이 일치한다.
return 1
i = i + numOfSkip
return 0
mydict = makebmt('test')
print(boymoreMatching('test',mydict,'asdasdtest'))
print(boymoreMatching('test',mydict,'text'))
##############출력
1
0
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
|
|
|
'2020 > Algorithm' 카테고리의 다른 글
| Python: 기초 문법 (0) | 2020.02.15 |
|---|---|
| Python: 선택 정렬, 삽입 정렬, 버블정렬, 병합정렬 (0) | 2020.02.15 |
| Python: Binary Search (이진탐색) (0) | 2020.02.15 |