C언어로 구현한 KMP 알고리즘

목차

1. 과제 목표
2. 설계
3. 결과 보고
4. 자료구조 및 알고리즘 분석
5. 전체 코드

본문내용

1. 과제 목표
- 두 개의 스트링(string, pat)을 입력으로 받아 pattern matching을 하는 KMP 알고리즘을 구현하시오.

2. 설계
- 스트링 안에 원하는 패턴을 찾는 가장 단순한 방법은 한 칸씩 대입하며 틀린 경우 1칸을 이동하여 다시 패턴의 처음부터 비교하는 경우입니다. 이 때의 복잡도는 스트링의 길이 M, 패턴의 길이 N이라고 했을 때, O(n*m)이 됩니다.
- 본 과제에서는 같은 작업에 대해 복잡도를 O(n+m)까지 줄일 수 있는 KMP 알고리즘 (KnuthMorris-Pratt Algorithm)을 강의자료에서 소개된 코드 그대로 사용했습니다. 사용한 자료 구조로는, 검색할 문자열 string과 패턴 문자열 pat, 그리고 정수형 failure 세 개의 배열을 사용했습니다.

3. 결과 보고
- Input으로 주어진 kmp.txt의 내용을 확인한 결과입니다.

4. 자료구조 및 알고리즘 분석
- MAX_STRING_SIZE와 MAX_PATTERN_SIZE는 각각 100으로 설정했으므로 찾을 문자열과 패턴은 100글자 이내의 배열로 선언됩니다. 함수는 failure 배열의 값을 설정하는 fail 함수와, 생성된 failure 배열의 값을 이용해 실제 패턴을 매칭하는 pmatch 함수로 나뉩니다.
파일 입출력을 통해 찾을 문자열과 패턴 문자열을 입력 받는 부분입니다. 또한 pat을 주소값 형태로 fail 함수에 넘긴 후 처리가 끝나면 pmatch 함수의 정수로 반환되는 결과값이 그대로 출력되도록 넘겨주었습니다.

참고자료

· 없음