1786 찾기 (1) 썸네일형 리스트형 문자열 매칭 알고리즘[2](KMP)[String Searching Algorithm, Knuth-Morris-Pratt] 먼저 이 문제(찾기, 1786)를 먼저 보고 오자. 백준에서 플5문제이고 KMP를 사용해야 되는 이유를 잘 설명해주고 있다. 문자열 매칭 알고리즘을 사용해서 문자열에서 패턴을 시간복잡도 O(|S|)으로 찾아보자. 파이썬에서는 kmp 관련 문제가 나오면 정규식(regex, re)으로 찾자^^. 1. KMP 알고리즘 정의 두 개의 문자열 P와 T에 대해, 문자열 P가 문자열 T 중간에 몇 번, 어느 위치에서 나타나는지 알아내는 문제를 '문자열 매칭'이라고 한다. KMP 알고리즘은 Knuth, Morris, Prett가 만든 문자열 매칭 알고리즘으로 시간복잡도는 O(N+M)으로 무식한 방법 O(NM)보다 매우 빠르다. 더보기 사람들은 이렇게 사람 성이 들어간 알고리즘을 두 가지 형태로 부른다. 첫 번째는 성을.. 이전 1 다음
