✓

태그:

33. 문자열 알고리즘 1 CLASS 6 ESSENTIAL

이건… KMP 알고리즘이라고 검색해봐야 할 것 같네요…

풀이 비스무리한거 보기

주어진 문자열에 안에 또 다른 주어진 문자열이 있는지, 있다면 몇 번 어디에 위치하는지 찾는 문제입니다. 그냥 단순하게 각 위치마다 문자열이 맞는지 체크하겠다고 생각할 수 있는데, 그러면 Gold Ⅰ 문제가 아닙니다. 만약 그렇게 푼다면 T 문자열의 길이를 t, P 문자열이 길이를 p라고 했을 때 대략 $O(tp)$ 정도의 시간이 걸립니다. 그런데 그 길이가 무려 100만씩이 가능하기 때문에 시간이 부족합니다. 이 때 사용할 수 있는 알고리즘이 KMP 알고리즘입니다. 이 알고리즘으로 풀면 대략 $O(t+p)$의 시간이 걸립니다. 이 알고리즘을 그대로 구현하면 정답을 맞출 수 있습니다.

※ KMP 알고리즘은 메모에서 나중에 다룰 예정입니다.

소스 코드

언어	코드	시간	비고
C++	코드(Github) / 코드(백준)	2021-01-30 22:45:04

---