몽상실현개발주의

[종만북] 문자열 검색 - KMP 알고리즘 / 문자열 문자열 검색 - KMP 알고리즘 단순한 알고리즘의 검색 과정에서 얻는정보를 이용하여 시간을 절약 할 수 있다. H 의 부분 문자열을 N 과 비교 시, N 의 첫 글자와 대응 되지 않는 H 의 부분문자열 위치를 시작 위치 후보들에서 제외 시키는 방법으로 구현하면 최적화가 가능하다. 이와 같은 방법은 커누스-모리스-프랫(Knuth-Morris-Pratt) 알고리즘이며, 흔히 KMP 알고리즘으로 부른다. H[i...i+matched-1] = N[...matched-1](접두사) 이 일치 할때, i < i+k < matched-1, H[i+k...i+matched-1] = N[K...] (접미사) 가 일치 한다면, N[K...] (접미사) = N[...mat..

[종만북] 문자열 검색 / 문자열 문자열 현대의 컴퓨터는 많은 양의 문자열 자료를 다룹니다. 문서 파일, 인터넷의 웹페이지. 이메일 그리고 문자 메시지들이 모두 다 문자열입니다. 때문에 문자열을 다루는 문제와 자료구조는 전산학의 중요한 연구 주제이며, 정보 검색 (Information retrieval) 이나 생물 정보학 (bioinformatics) 분야에서 특히 이용하게 사용됩니다. 문자열을 다루는 알고리즘 또한 매우 범위가 깊고 넓지만, 시간이 제한된 프로그래밍 대회 특성상 구현이 비교적 간단한 알고리즘이 주로 사용 됩니다. - KPM 알고리즘 : 문자열 검색 - 접미사 배열 (suffix array) : 문자열 처리 용어에 관하여 문자열의 부분 문자열(substring), 접두사(prefix), ..