1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net [문제 설명] [문제 풀이] 해당 문제는 KMP알고리즘을 이용하여 문자열 패턴 매칭을 하는 문제이다. 따라서 KMP 알고리즘에 대한 이해가 필요하다. 혹시 해당 알고리즘에 대해 잘 모른다면 아래 포스트를 참고하길 바란다. [Algorithm] - 문자열 탐색 알고리즘 : KMP 이론 KMP 알고리즘이란, 문자열 탐색 알고리즘으로써 알고리즘을 만든 사람들(Knuth-Morris-Pratt)의 앞글자를 딴 것이다. 웹페이지에서 ctrl + F를 이용하여 문자열..

이론 KMP 알고리즘이란, 문자열 탐색 알고리즘으로써 알고리즘을 만든 사람들(Knuth-Morris-Pratt)의 앞글자를 딴 것이다. 웹페이지에서 ctrl + F를 이용하여 문자열을 검색할 때, 특정 단어를 검색엔진에서 검색할때도 사용될 수 있다. 해당 알고리즘의 시간복잡도는 O(N+M)을 가진다. 구현 KMP 알고리즘은 접두사(prefix)와 접미사(suffix)의 개념을 활용하여 실패함수 테이블을 만들고, 테이블을 활용하여 반복되는 문자열을 건너뛰면서 패턴을 찾는 알고리즘이다. 접두사와 접미사에 대해 간단하게 정리해보고자 예를 들어보겠다. "abacabab"라는 문자열이 있다고 가정하자. 우리는 각 문자의 길이에 따라 접두사와 접미사가 일치하는 최대 길이를 테이블에 저장할 것이다. 실패함수 테이블을..