문자열 검색 알고리즘

🚩 문자열에서 부분 문자열을 검색하는 알고리즘을 배워보자. 

문제 설명 - 1543번 문제 검색

첫째 줄에 문서가 주어진다. 문서의 길이는 최대 2500이다. 둘째 줄에 검색하고 싶은 단어가 주어진다. 이 길이는 최대 50이다. 문서와 단어는 알파벳 소문자와 공백으로 이루어져 있다. 문서에서 단어가 최대 몇 번 중복되지 않게 등장하는지 구하는 프로그램을 작성하시오.

입력

ababababa
aba

출력

2

문자열(텍스트)에서 부분문자열(패턴)을 찾는 방법은 브루트 포스, KMP, 보이어 무어법으로 풀이할 수 있다.

브루트 포스법

문자열 검색 알고리즘에서 가장 기초적이고 단순한 방법이다.
텍스트에서 패턴을 순차적으로 검색하는 방법이다.

• 시간복잡도 : O(Mn)

단순한 방식으로 텍스트의 하나하나를 반복문으로 돌려서 푼다.

코드

#문자열 #브루트 포스 알고리즘

text = list(input())
pattern = list(input())

result = 0
i = 0
j = 0

#리스트의 인덱스를 꺼내는 함수가 있을 것이다.
while i < len(text) - len(pattern) + 1:
    temp = 0
    for j,p in enumerate(pattern):
        if text[i+j] != pattern[j]:
            break
        else:
            temp += 1
    if temp == len(pattern):
        result += 1
        i += len(pattern)
    else:
        i += 1

print(result)