BACKJOON 1543번 (문서 검색)

문서가 있을 때, 단어를 찾는 문제, 동시에 셀 수 없기에 하나의 단어만 찾을 수 있다. 

예제 입력1 같은 경우  aba aba가 두번 찾을 수 있기에 예제출력에서 2와 같은 것이 나오고, 

예제 입력2 같은 경우 aa가 두번 있기에 2번

예제 입력3 같은 경우 ababa가 한번 있기에 1

예제 입력4 같은 경우 aa가 매치가 안되는 것 없이 전부 매치되기에 3이 출력된다. 

 

문서의 길이는 최대 2,500이고 단어의 길이는 최대 50이다.

그러면 단순하게 모든 경우의 수를 계산하여 문제를 해결 가능 하다. 그럼 시간복잡도 O(NM)의 알고리즘으로 해결 가능하다. 모든 경우를 탐색해도 약 10만정도의 작은 수 이기 때문이다. 

document = input()
word = input()

index = 0
result = 0

while len(document) - index >= len(word):
    if document[index:index + len(word)] == word: # 문서에서 보고 있는 단어가 찾고자 하는 단어인 경우
        result += 1
        index += len(word)
    else:
        index += 1
 
print(result)

index = 0을 만들어 줌으로 써 index 0부터 차례대로 비교할 수 있도록 설계를 시작한다.

이후 while문을 통해서 단어가 벗어나지 않을 때 까지 반복을 해주면서, 비교를 할 때 마다 문서에서 index부터 단어의 길이만큼 확인을 해서 == word로 단어와 정확히 일치하는지,만약 찾고자 하는 단어와 일치하는 경우 단어의 길이만큼 ( index += len(word) )를 통해서  index를 더해준다. 찾지 못한 경우,

 else:
        index += 1

로 한칸만 이동하게 만든다.