KMP 알고리즘 (문자열 패턴 검색)

KMP

- 접두부, 접미부, 경계 세개의 개념이 중요.

Ex)

BAABABAAC 라는 패턴이 존재 할 때.

C라는 마지막글자에서 틀렸다면,

맞은 글자들을 대상으로, 위와같이 확인한다.

BAA  BA  BAA

접두부 경계 접미부

접두부와 접미부가 같으면서, 경계의 길이가 최소가 될때의

접두.미부의 길이를 최대 너비라 한다.

- 알고리즘의 요지

 : 100글자의 문자열 S, 10글자의 P가 있을 때,

S의 처음부터 하나씩 다 확인해볼필요가 없이,

확인할 필요가없는 부분은 점프를 해서, 성능향상을 얻는다.

1) S와 P를 한글자씩 비교해 나간다.

 1.1) 끝까지 모두 같으면 패턴을 찾은 것이다.

 1.2) 틀린 부분의 위치를 k라 할 때.

      1~k-1까지의 패턴값을 가지고, 경계를 찾는다.

2) 경계의 길이가 최소가 되는

   접두부,접미부를 구한 다음. 

   접두부를 접미부 시작위치로 옮긴 후 패턴을 다시 시작해서 비교 한다.(

(출처 : http://carstart.tistory.com/143)

일치한 글자의 수 n	0	1	2	3	4	5	6	7	8
문자 c	B	A	A	B	A	B	A	A
경계의 길이가 최대가 되는 접두.미사의 길이 ( 접두 = 접미사의 길이) L	-1	0	0	0	1	2	1	2	3
이동해야할 거리 S (s = n-L)	1	1	2	3	3	3	5	5

이동거리 테이블을 만들어야 한다. 위와같이..

우선, 맞는글자가 하나도 없는 경우의 L은 -1이다.: 공식 s=n-L에 맞추기 위해서는 정해져있다 값이.

위와 같이 처음에 테이블만 한번 구성 한 후,

패턴이 몇글자맞았는지에 따라 옆으로 S만큼 이동하면서 패턴이 다 맞는경우를 찾으면된다.

 

 

예제 문제)

 

집합 S는 N가지 문자열의 집합이다. Q개의 문자열이 주어질 때, 각 문자열의 부분 문자열이 하나라도 S에 속하는지 아닌지 판별하는 프로그램을 작성하라. 예제를 예로 들면 S= {"www","woo","jun"}일때, “myungwoo”의 부분 문자열 중 하나인 “woo”가에 속하므로 답은 ‘Y’이고, “hongjun”의 부분 문자열 중 하나인 “jun”이 에 속하므로 답은 ‘Y’이다. 하지만 “dooho”는 어떤 부분 문자열도 S에 속하지 않으므로 답은 ‘N’이다. 이 답을 이어 붙여서 “YYN”을 출력하면 된다.   입력 첫째 줄에는 테스트케이스의 개수 T가 주어지며 둘째 줄부터 각 테스트케이스가 주어진다. 각 테스트케이스의 첫째 줄에는 N(1 ≤ N ≤ 1,000)이 주어진다. 다음 N개의 줄에는 S에 속하는 길이 100 이하의 문자열들이 주어진다. 다음 줄에는 Q(1 ≤ Q ≤ 1,000)가 주어진다. 다음 Q개의 줄에는 답을 판별해야 하는 길이 10,000 이하의 문자열들이 주어진다. 입력으로주어지는 문자열은 모두 알파벳 소문자로 이루어져 있다.   출력 각 테스트케이스 마다 정답을 의미하는 Q자리의 문자열을 출력한다.   입력 예제 1 3 www woo jun 3 myungwoo hongjun dooho 출력 예제 YYN   main.cpp input_test.txt