Programming/Algorithm
-
[Algorithm] KMPProgramming/Algorithm 2020. 11. 23. 06:34
def kmp_match(txt:str,pat:str)->int: #txt는 원본 텍스트를 말하며 pat는 비교되어지는 패턴을 말합니다. """KMP법으로 문자열 검색하기""" pt=1 #txt를 따라가는 커서 pp=0 #패턴을 따라가는 커서 skip=[0]*(len(pat)+1) ###########과제 : length 길이에 왜 +1 인지? # ABCABD를 예로 들었을 때 # 이 소스코드에서는 TXT가 1부터 시작할 때 PP 0과 1의 값을 먼저 비교하며 # 건너 뛰기 테이블에 인덱스를 TXT와 같이 쓰기 위해서 씁니다. # 즉 TXT (PT)와 0부터 비교하지않고 SKIP과 인덱스를 맞추려니 # PT의 값도 +를 먼저 해주기 때문에 마지막으로 가면 인덱스가 6을 커서해서 # SKIP의 6 인덱스를..
-
[Algorithm] Brute Force MethodProgramming/Algorithm 2020. 11. 23. 06:29
def bf_match(txt:str, pat:str)->int: pt=0 pp=0 #일단 텍스트를 따라가는 pt와 #패턴을 따라가는 pp 를 0으로 초기화 했습니다. while pt!=len(txt) and pp!=len(pat): #그리고 pt가 텍스트크기를 다 탐색하거나 #패턴커서가 패턴의 크기를 다 탐색했을경우 #while문을 종료합니다. if txt[pt]==pat[pp]: pt+=1 pp+=1 #만약 텍스트커서와 패턴에 있는 커서를 비교해서 #둘이 일치할경우 커서를 이동해도 문제가 없다! #그리고 다음 비교를 수행합니다. else: pt=pt-pp+1 pp=0 #일치하지 않을 경우에는 #여기서는 텍스트나 패턴의 문자를 다 탐색하지 않을경우니까 # 패턴 문자열이 탐색이 다 되지 않을 경우 # 이..