백준 파이썬 1543번: 문서 검색

www.acmicpc.net/problem/1543

1543번: 문서 검색

문제 유형: 문자열, 브루트 포스 알고리즘

 

# Solution 1

d = input()
w = input()

index = 0
count = 0

while len(d) - index >= len(w):
    if d[index: index + len(w)] == w:
        count += 1
        index += len(w)
    else:
        index += 1
print(count)

1. 현재 인덱스 값에서부터 인덱스 값과 단어 길이의 수를 더한 인덱스까지가 주어진 단어인지 파악한다.
2. 만약 문서가 abababa이고 단어가 aba이면, abababa 첫 번째 글자부터 세 번째 글자까지가 aba라는 것을 파악할 수 있다.
3. 같은 것을 확인했다면 중복을 피하기 위해 현재 인덱스에서 단어 길이를 더해준다.
4. abababa와 aba의 경우 0에서 3을 더한 네 번째 글자부터 다시 검색을 시작한다.
5. 만약 문서에 주어진 단어와 완벽하게 일치하는 구간이 없다면 인덱스를 1씩 늘려가며 검색을 계속한다.
6. 문서 길이와 현재 인덱스 번호의 차가 단어 길이보다 작아질 때까지 반복해준다. 남은 구간이 단어의 글자 수보다 작아진다면 어차피 단어와 일치하는 구간이 없는 것이므로 더 이상 검색이 무의미해진다.