백준#1543 문서 검색

문제

https://www.acmicpc.net/problem/1543

나의 풀이

line = input()
target = input()


search_line = line
count = 0
while search_line:
    if search_line.startswith(target):
        count += 1
        search_line = search_line[len(target):]
    else:
        search_line = search_line[1:]

print(count)

남의 풀이

• 문서의 길이는 최대 2,500이고, 단어의 길이는 최대 50
• 단순히 모든 경우의 수를 계산하여 문제를 해결할 수 있음
• 시간 복잡도 O(NM)의 알고리즘으로 해결할 수 있음
• 2500 * 50는 10만으로 파이썬은 최대 50만까지 처리가능
  

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)