크누스-모리스-프랫 알고리즘

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

컴퓨터 과학에서, 크누스-모리스-프랫 알고리즘(Knuth–Morris–Pratt algorithm)은 문자열 중에 특정 패턴을 찾아내는 문자열 검색 알고리즘의 하나이다. 주먹구구식 알고리즘에서 불필요한 문자간 비교를 없애기 위해 Next 데이터라고 하는 패턴 정보를 활용하여 검색 시간을 단축하는 방식이다.