KMP 알고리즘 - 구름LEVEL
KMP 알고리즘
Quiz Info
Quiz Info
KMP 알고리즘
100points
Participant
15
Solved Rate
66.6%
1
0

문자열 관련 알고리즘 중 가장 이해하기 힘든 알고리즘 중 하나인 KMP 알고리즘에 대한 문제입니다.


KMP 알고리즘이란 ?

발견자들인 Knuth-Morris-Pratt의 앞글자를 따서 KMP라고 하며, 간단하게 설명하자면 비교할 필요가 없는 부분은 패스하고 필요한 부분만 비교를 수행하는 것이 핵심인데 자세한 원리는 다음과 같습니다.

문자열의 머리 부분인 접두부(Prefix)와 꼬리 부분인 접미부(Suffix)에 대해 먼저 알아보겠습니다.

\

위의 그림을 참고하면 'BAABABBA'라는 문자열을 기준으로 위의 왼쪽 문자들은 접두부가 될 수 있고, 오른쪽 문자들은 접미부가 될 수 있습니다.

* 혼동하면 안될 부분이 접미부를 뒤에서 부터 읽는 것이 아니라 앞에서 부터 읽는 다는 점 입니다( 3번째 접미부가 'BAA'인 것 참고할 것 ).

여기서 알아야할 개념이 접두부와 접미부의 '경계'인데 접두부와 접미부가 같을 때 가운데 낀 문자(열)을 경계라고 생각하시면 됩니다( 3번째의 경우 두'BAA' 사이의 BA가 경계 ).


이제 KMP 알고리즘에 대한 핵심이 나옵니다.

1. 비교할 패턴을 문자열의 처음에 위치시킨다.

2. 오른쪽으로 진행하면서 비교한다(일치하면 성공 / 불일치하면 다음 단계 진행).

3. 일치하지 않는 부분의 왼쪽 부분을 가지고 경계를 찾는다( 찾으면 다음으로 이동 / 찾지 못하면 문자열 패턴의 틀린 부분만큼 이동 ).

4. 경계를 찾았다면 접미부와 접두부가 있을 것입니다.. 경계가 2개 이상일 경우는 처리를 해주어야 합니다. 접두부와 접미부가 있다면 그 접두부 길이의 접두부 시작 위치에서 접미부 위치로 이동을 시켜줍니다.

5. 2로 이동하여 반복 수행


KMP 알고리즘을 통해 첫 줄에 입력한 문자열 안에 다음 줄에 입력한 문자열이 존재하는지를 검사하고 존재할 경우 'Exist', 존재하지 않을 경우 'Not Exist'를 출력하는 프로그램을 작성하십시오.


입력

첫 줄에 검사의 대상이 되는 문자열

둘째 줄에 검사할 문자열

출력

둘째 줄에 입력한 문자열이 첫째 줄에 입력한 문자열에 포함될 경우 'Exist', 그렇지 않을 경우 'Not Exist'


Input/Output Example
:
Blank
:
Line Break
:
Tab
Example 1
Input
whenever
what
Output
NotExist
Example 2
Input
wherever
where
Output
Exist
⋇ Please keep the input and output formats carefully
Quiz Info
Q & A
Q&A forum that anyone can ask and answer.
Share your questions and answers with other students and grow together!

Registered Questions(0)