9강. 문자열 알고리즘

9. 문자열 알고리즘

---

9.1 문자열 검색

문자열 검색(String Searching)
문자열 검색 알고리즘은 텍스트 내에서 특정 패턴 문자열을 찾는 문제입니다. 문자열 검색은 텍스트 편집기, 검색 엔진, 바이오인포매틱스 등에서 광범위하게 사용됩니다. 기본적인 문자열 검색 알고리즘은 브루트 포스(Brute Force) 알고리즘이 있습니다.

역사적 배경
문자열 검색 문제는 컴퓨터 과학의 초창기부터 중요하게 여겨졌습니다. 초기의 간단한 알고리즘들은 효율성 문제로 인해 더 나은 알고리즘들이 개발되었습니다.

// 브루트 포스 문자열 검색 예시
public class BruteForceSearch {
    /**
     * 주어진 텍스트에서 패턴을 찾는 브루트 포스 알고리즘
     *
     * @param text   검색할 텍스트
     * @param pattern 찾을 패턴
     * @return 패턴이 시작되는 인덱스, 찾지 못한 경우 -1
     */
    public static int search(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();

        for (int i = 0; i <= n - m; i++) {
            int j;
            for (j = 0; j < m; j++) {
                if (text.charAt(i + j) != pattern.charAt(j))
                    break;
            }
            if (j == m)
                return i; // 패턴이 시작되는 인덱스 반환
        }
        return -1; // 패턴을 찾지 못한 경우
    }

    public static void main(String[] args) {
        String text = "ABABDABACDABABCABAB";
        String pattern = "ABABCABAB";
        int result = search(text, pattern);

        if (result != -1)
            System.out.println("Pattern found at index " + result);
        else
            System.out.println("Pattern not found");
    }
}

이 코드에서 우리는 브루트 포스 알고리즘을 사용하여 텍스트 내에서 패턴을 찾습니다. 이 알고리즘은 텍스트의 각 위치에서 패턴을 하나씩 비교하여 찾습니다.

9.2 접미사 배열과 접미사 트리

접미사 배열과 접미사 트리(Suffix Array and Suffix Tree)
접미사 배열과 접미사 트리는 문자열의 접미사들을 정렬된 순서로 저장하는 자료구조입니다. 이 자료구조들은 문자열의 패턴 매칭, 반복 부분 문자열 찾기, 문자열의 사전순 순위 계산 등에 사용됩니다.

접미사 배열의 시간 복잡도는 \(O(n \log n)\)이며, 접미사 트리의 시간 복잡도는 \(O(n)\)입니다.

역사적 배경
접미사 트리는 1973년 Weiner에 의해 처음 소개되었고, 접미사 배열은 1990년에 Manber와 Myers에 의해 개발되었습니다. 이 자료구조들은 문자열 알고리즘 연구에서 중요한 역할을 합니다.

// 접미사 배열 생성 예시
import java.util.Arrays;

public class SuffixArray {
    /**
     * 주어진 문자열의 접미사 배열을 생성하는 함수
     *
     * @param text 생성할 문자열
     * @return 접미사 배열
     */
    public static int[] buildSuffixArray(String text) {
        int n = text.length();
        Suffix[] suffixes = new Suffix[n];

        for (int i = 0; i < n; i++) {
            suffixes[i] = new Suffix(i, text.substring(i));
        }

        Arrays.sort(suffixes);

        int[] suffixArr = new int[n];
        for (int i = 0; i < n; i++) {
            suffixArr[i] = suffixes[i].index;
        }

        return suffixArr;
    }

    static class Suffix implements Comparable {
        int index;
        String suffix;

        Suffix(int index, String suffix) {
            this.index = index;
            this.suffix = suffix;
        }

        @Override
        public int compareTo(Suffix o) {
            return this.suffix.compareTo(o.suffix);
        }
    }

    public static void main(String[] args) {
        String text = "banana";
        int[] suffixArray = buildSuffixArray(text);

        System.out.println("Suffix Array for " + text + ":");
        System.out.println(Arrays.toString(suffixArray));
    }
}

이 코드에서 우리는 주어진 문자열의 접미사 배열을 생성합니다. 접미사를 사전순으로 정렬하여 배열에 저장합니다.

9.3 KMP 알고리즘

KMP 알고리즘(Knuth-Morris-Pratt Algorithm)
KMP 알고리즘은 문자열 검색 알고리즘으로, 패턴 내에서 중복된 부분을 활용하여 효율적으로 검색을 수행합니다. KMP 알고리즘의 시간 복잡도는 \(O(n + m)\)입니다.

역사적 배경
KMP 알고리즘은 1977년에 Donald Knuth, Vaughan Pratt, James H. Morris에 의해 개발되었습니다. 이 알고리즘은 문자열 검색 문제의 효율성을 크게 향상시켰습니다.

// KMP 알고리즘 예시
public class KMPAlgorithm {
    /**
     * 주어진 텍스트에서 패턴을 찾는 KMP 알고리즘
     *
     * @param text   검색할 텍스트
     * @param pattern 찾을 패턴
     * @return 패턴이 시작되는 인덱스, 찾지 못한 경우 -1
     */
    public static int KMPSearch(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        int[] lps = computeLPSArray(pattern);

        int i = 0, j = 0;
        while (i < n) {
            if (pattern.charAt(j) == text.charAt(i)) {
                i++;
                j++;
            }
            if (j == m) {
                return i - j; // 패턴이 시작되는 인덱스 반환
            } else if (i < n && pattern.charAt(j) != text.charAt(i)) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
        return -1; // 패턴을 찾지 못한 경우
    }

    private static int[] computeLPSArray(String pattern) {
        int m = pattern.length();
        int[] lps = new int[m];
        int len = 0;
        int i = 1;
        lps[0] = 0;

        while (i < m) {
            if (pattern.charAt(i) == pattern.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }

    public static void main(String[] args) {
        String text = "ABABDABACDABABCABAB";
        String pattern = "ABABCABAB";
        int result = KMPSearch(text, pattern);

        if (result != -1)
            System.out.println("Pattern found at index " + result);
        else
            System.out.println("Pattern not found");
    }
}

이 코드에서 우리는 KMP 알고리즘을 사용하여 텍스트 내에서 패턴을 찾습니다. KMP 알고리즘은 패턴 내에서 중복된 부분을 활용하여 효율적으로 검색을 수행합니다.

9.4 라빈-카프 알고리즘

라빈-카프 알고리즘(Rabin-Karp Algorithm)
라빈-카프 알고리즘은 해시 함수를 사용하여 문자열 검색을 수행하는 알고리즘입니다. 주어진 패턴의 해시 값을 계산한 후, 텍스트의 각 부분 문자열의 해시 값과 비교하여 패턴을 찾습니다. 라빈-카프 알고리즘의 평균 시간 복잡도는 \(O(n + m)\)입니다.

역사적 배경
라빈-카프 알고리즘은 1987년에 Richard M. Karp와 Michael O. Rabin에 의해 개발되었습니다. 이 알고리즘은 해시 함수를 사용하여 문자열 검색의 효율성을 높였습니다.

// 라빈-카프 알고리즘 예시
import java.math.BigInteger;
import java.util.Random;

public class RabinKarpAlgorithm {
    private final static int d = 256; // 알파벳의 크기 (ASCII)

    /**
     * 주어진 텍스트에서 패턴을 찾는 라빈-카프 알고리즘
     *
     * @param text   검색할 텍스트
     * @param pattern 찾을 패턴
     * @param q 소수 (충돌 방지를 위한 모듈러 연산)
     * @return 패턴이 시작되는 인덱스, 찾지 못한 경우 -1
     */
    public static int search(String text, String pattern, int q) {
        int n = text.length();
        int m = pattern.length();
        int i, j;
        int p = 0; // 패턴의 해시 값
        int t = 0; // 텍스트의 해시 값
        int h = 1;

        // 해시 값을 계산하기 위한 h의 초기 값 설정 (h = d^(m-1) % q)
        for (i = 0; i < m - 1; i++)
            h = (h * d) % q;

        // 패턴과 텍스트의 첫 번째 창의 해시 값을 계산
        for (i = 0; i < m; i++) {
            p = (d * p + pattern.charAt(i)) % q;
            t = (d * t + text.charAt(i)) % q;
        }

        // 텍스트에서 패턴을 찾기 위한 슬라이딩 윈도우
        for (i = 0; i <= n - m; i++) {
            if (p == t) { // 해시 값이 일치하는 경우
                for (j = 0; j < m; j++) {
                    if (text.charAt(i + j) != pattern.charAt(j))
                        break;
                }

                if (j == m)
                    return i; // 패턴이 시작되는 인덱스 반환
            }

            // 다음 창의 해시 값을 계산 (슬라이딩 윈도우)
            if (i < n - m) {
                t = (d * (t - text.charAt(i) * h) + text.charAt(i + m)) % q;

                if (t < 0)
                    t = (t + q);
            }
        }

        return -1; // 패턴을 찾지 못한 경우
    }

    public static void main(String[] args) {
        String text = "GEEKS FOR GEEKS";
        String pattern = "GEEK";
        int q = 101; // 소수

        int result = search(text, pattern, q);

        if (result != -1)
            System.out.println("Pattern found at index " + result);
        else
            System.out.println("Pattern not found");
    }
}

이 코드에서 우리는 라빈-카프 알고리즘을 사용하여 텍스트 내에서 패턴을 찾습니다. 해시 함수를 사용하여 패턴과 텍스트의 각 부분 문자열을 비교하며, 해시 값이 일치할 경우에만 실제 문자열을 비교합니다.

 

역사적 배경과 개념이 생겨나게 된 이유

문자열 알고리즘은 컴퓨터 과학의 기본 문제 중 하나로, 초기 컴퓨터 과학자들은 텍스트와 패턴 매칭 문제의 효율적인 해결 방법을 찾기 위해 연구했습니다. 문자열 알고리즘의 주요 목표는 텍스트 내에서 패턴을 신속하게 찾는 것입니다.

브루트 포스 알고리즘은 가장 단순한 형태의 문자열 검색 알고리즘으로, 모든 가능한 위치에서 패턴을 비교합니다. 이는 매우 비효율적이므로, 이를 개선하기 위한 다양한 알고리즘이 개발되었습니다.

접미사 배열과 접미사 트리는 문자열의 접미사들을 사전순으로 정렬하여 다양한 문자열 문제를 효율적으로 해결할 수 있도록 합니다. 이들은 문자열의 부분 문자열 검색, 중복 부분 문자열 찾기, 문자열의 사전순 순위 계산 등에서 유용하게 사용됩니다.

KMP 알고리즘은 패턴 내의 중복된 부분을 활용하여 효율적으로 검색을 수행합니다. 이는 패턴 매칭 문제의 효율성을 크게 향상시켰습니다. KMP 알고리즘은 패턴 내에서 접두사와 접미사를 비교하여 중복된 비교를 줄입니다.

라빈-카프 알고리즘은 해시 함수를 사용하여 문자열 검색의 효율성을 높입니다. 해시 함수를 사용하여 패턴과 텍스트의 부분 문자열을 비교하며, 해시 값이 일치할 경우에만 실제 문자열을 비교합니다. 이는 충돌을 최소화하여 검색 시간을 단축시킵니다.

---

해시태그: #알고리즘 #Algorithm #프로그래밍 #Programming #컴퓨터과학 #ComputerScience #코딩 #Coding #문자열알고리즘 #StringAlgorithm #문자열검색 #StringSearching #접미사배열 #SuffixArray #접미사트리 #SuffixTree #KMP알고리즘 #KMPAlgorithm #라빈카프알고리즘 #RabinKarpAlgorithm #Java #자바 #코딩공부 #개발자 #Developer