PS (1) 썸네일형 리스트형 KMP 알고리즘 알고리즘 소개 KMP 알고리즘은 특정 문자열에서 특정 문자열의 패턴이 존재하는가를 판단할때 유용하다. ex) "AAABCCDEFSDFSWESSSAAWWSSW" 문자열에서 ABC 문자열이 존재하는지를 찾기 위해서는 일반적으로 찾기위해서 N*M 번 모든경우를 뒤저야한다. 하지만 KMP 알고리즘을 사용한다면 훨씬 빠르게 pattern을 찾을 수 있다. 여기서는 접미사와 접두사의 개념을 이해해야한다. 접두사 : 문자열의 앞쪽 접미사 : 문자열의 끝쪽 즉 찾을 문자열의 접두사와 접미사의 비교를 통해 반복적으로 일어나는 문자열의 길이와 위치를 알수 있으면 실제 문자열에서 찾을때 처음부터 다시 찾는것이아니라 반복적으로 일어난 패턴에대해서는 이미 같을 것이니깐 거기서부터찾는 것이다. ex) ABDABC 라는 무자열 이.. 이전 1 다음
