문자열 검색 - 브루트 포스(brute force)

단순 무식하게 처음부터 끝까지 찾는 방식이다.

위 그림에서 txt는 내가 찾고자하는 pat가 포함된 데이터로 ABABCDEFGHA이다. pat는 txt에서 찾고자하는 pattern으로 ABC이다.

이 때 pt는 txt의 원소를 가리키는 커서이고, pp는 pat의 원소를 가리키는 커서이다. pt가 가리키는 원소와 pp가 가리키는 원소가 동일하다면 옆으로 같이 +1씩 이동하여 다음 문자열을 비교해보면 된다. 그러다가 일치하지 않으면 pt는 이동했던 만큼 돌아와야 한다. 이는 pp만큼 움직였다는 뜻이기 때문에 pt - pp를 하면 비교하기 전으로 돌아온다. 여기서 + 1을 하면 pt는 비교하기 전으로 돌아오고 오른쪽으로 1만큼 이동하게 된다.

원하는 원소(여기서 ABC라고 한다면)를 찾았다면 while문을 돌고나서 pt = 5, pp = 3이 되어있을 것이다. pp != len(pat)를 만족시키지 못하기 때문에 (pp는 len(pat)와 같으므로 !=을 만족시키지 못한다) while이 끝나게 된다.

pp랑 len(pat)가 같다는 뜻은 커서가 pat의 길이만큼 다 이동을 했고 이는 while문 안의 if문을 만족시키고 while을 빠져나왔다는 뜻이다. 이것은 원하는 문자를 다 찾았다는 뜻이 된다. 찾지 못했다면 계속 while 문을 돌 것이다.

ABC를 찾는다치면 while문을 나올 때 pt가 5가 되어 있을 것이다. 이때 pp만큼 빼주면 비교를 시작했던 index가 된다.

소스 코드

def bf_match(txt, pat):                 # txt : 기존 string 데이터, pat : 찾고자하는 string 데이터
    pt = 0                              # txt를 따라가는 커서
    pp = 0                              # pat를 따라가는 커서

    while pt != len(txt) and pp != len(pat):
        if txt[pt] == pat[pp]:
            pt += 1
            pp += 1
        else:
            pt = pt - pp + 1            # pt랑 pp가 같이 이동한 만큼을 빼줘고(원래 자리로 돌아옴) + 1을 해주면 옆으로 pt가 이동한다.
            pp = 0                      # pp는 다시 처음부터
    print('--')
    print('pt', pt)
    print('pp', pp)

    if pp == len(pat):
        return pt - pp                  # 3번 다 통과를 했으면 pp는 0에서 1, 1에서 2, 2에서 3이 되었을 것이다.
    else:
        return -1                       # 3번 다 통과를 못했으면 pp는 2나 1 혹은 0일 것이다.

txt = input()
pat = input()

idx = bf_match(txt, pat)
print('--')
if idx == -1:
    print('텍스트 안에 패턴이 존재하지 않습니다.')
else:
    print(f'{idx + 1}번째 문자부터 일치합니다.')        # 문자열에서는 첫번째 문자가 0 index이지만, 사람이 받아들일 때 첫 문자는 1번째이다.
    

# string = 'abcde'

# print(string.find('cd'))				# 2,  단순히 find를 이용해서도 찾을 수 있다.
# print(string.find('ddf'))				# -1

# print('cd' in string)					# True
# print('ddf' in string)				# False