알고리즘/문자열
2020. 7. 21.
KMP
대부분의 문자열 알고리즘은 어떤 문자열이 주어졌을 때, 이 부분 문자열 중 조건에 만족하는 특정한 문자열을 찾는 알고리즘입니다. 가장 단순하게, 문자열 \(S\)에서 문자열 \(T\)를 찾는 방법에 대해 알아봅시다. 문자열을 검색하는 가장 단순한 방법은, 이중 포문을 돌려 \(O(|S||T|)\)의 시간복잡도로 검색하는 것입니다. https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m번 문자가 차례로 � www.acmicpc.net 하지만 \(S\)와 \(T\)의 길이가 각각 최대 100만..
