코딩 테스트 대비: KMP 알고리즘을 활용한 문자열 검색 (C#)

안녕하세요, GameLabMaster입니다! 이번 코딩 테스트 대비 포스팅에서는 문자열 알고리즘 중 KMP(Knuth-Morris-Pratt) 알고리즘을 활용한 문제 풀이에 대해 알아보겠습니다. KMP 알고리즘은 문자열 검색에서 효율적인 방법으로, 브루트 포스 방식보다 빠른 속도로 문자열 검색을 수행할 수 있습니다.

 

문제

주어진 문자열 S와 패턴 문자열 P가 있을 때, S 안에 P가 존재하는지 확인하고, 존재한다면 몇 번째 인덱스에서 시작하는지 찾는 프로그램을 작성하세요.

 

입력

• 문자열 S (1 ≤ |S| ≤ 100,000)
• 문자열 P (1 ≤ |P| ≤ 10,000)
• 문자열은 알파벳 소문자로만 이루어져 있다.

출력

• 문자열 S 안에 패턴 문자열 P가 존재한다면 시작하는 인덱스를 출력하고, 존재하지 않는다면 -1을 출력합니다.

풀이
KMP 알고리즘은 패턴 문자열의 접두사와 접미사를 활용하여 불일치가 발생했을 때, 얼마나 건너뛰어야 하는지를 미리 계산하여 문자열 검색을 빠르게 수행할 수 있습니다.

다음은 C#으로 작성한 KMP 알고리즘을 사용하여 문자열 검색을 수행하는 코드입니다.

 

using System;
using System.Collections.Generic;

class Program {
    static int[] GetFailureFunction(string pattern) {
        int m = pattern.Length;
        int[] f = new int[m];
        int j = 0;

        for (int i = 1; i < m; i++) {
            while (j > 0 && pattern[i] != pattern[j]) {
                j = f[j - 1];
            }

            if (pattern[i] == pattern[j]) {
                f[i] = ++j;
            }
        }

        return f;
    }

    static List<int> KMP(string text, string pattern) {
        List<int> result = new List<int>();
        int[] f = GetFailureFunction(pattern);
        int n = text.Length;
        int m = pattern.Length;
        int j = 0;

        for (int i = 0; i < n; i++) {
            while (j > 0 && text[i] != pattern[j]) {
                j = f[j - 1];
            }

            if (text[i] == pattern[j]) {
                if (j == m - 1) {
                    result.Add(i - m + 1);
                    j = f[j];
                } else {
                    j++;
                }
            }
        }

        return result;
    }

    static void Main(string[] args) {
        string text = Console.ReadLine();
        string pattern = Console.ReadLine();
        List<int> result = KMP(text, pattern);

        if (result.Count > 0) {
            Console.WriteLine(string.Join(" ", result));
        } else {
            Console.WriteLine("-1");
        }
    }
}

 

이 코드는 먼저 실패 함수를 구한 후, KMP 알고리즘을 이용해 문자열 검색을 수행합니다. 실패 함수는 패턴 문자열의 접두사와 접미사가 일치하는 최대 길이를 계산하여 배열에 저장하는 함수입니다.

 

그 후, KMP 알고리즘을 사용해 주어진 텍스트에서 패턴 문자열을 찾습니다. 패턴 문자열이 발견되면 결과 리스트에 인덱스를 추가하고, 최종 결과를 출력합니다.

 

이제 이 코드를 이용하여 문자열 검색 문제를 효율적으로 해결할 수 있습니다. 다음 포스팅에서는 다른 문자열 알고리즘 문제와 풀이 방법을 다루겠습니다. 코딩 테스트 준비에 화이팅하세요