[알고리즘]문자열 알고리즘: 패턴 매칭, 트라이✏️✨

반응형

문자열 알고리즘은 컴퓨터 과학에서 데이터를 빠르고 정확하게 처리하기 위한 필수 도구입니다. ✨ 여기에서는 대표적인 문자열 알고리즘과 자료구조를 살펴보고, 각 알고리즘의 핵심 포인트와 활용법을 자세히 알아보겠습니다! 🚀

---

1. 패턴 매칭

패턴 매칭은 문자열에서 특정 패턴을 빠르게 찾는 기술입니다. 주요 알고리즘으로 KMP 알고리즘과 라빈-카프 알고리즘이 있습니다.

🎯 KMP (Knuth-Morris-Pratt) 알고리즘

KMP 알고리즘은 문자열 검색에서 중복 계산을 피하기 위해 접두사와 접미사 정보를 활용합니다. 효율적이고 안정적인 패턴 매칭 방법입니다.

✏️ 코드

public int[] computeLPS(String pattern) {
    int m = pattern.length();
    int[] lps = new int[m];
    int len = 0;
    int i = 1;

    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 void KMP(String text, String pattern) {
    int n = text.length();
    int m = pattern.length();
    int[] lps = computeLPS(pattern);

    int i = 0, j = 0;
    while (i < n) {
        if (text.charAt(i) == pattern.charAt(j)) {
            i++;
            j++;
        }

        if (j == m) {
            System.out.println("Pattern found at index: " + (i - j));
            j = lps[j - 1];
        } else if (i < n && text.charAt(i) != pattern.charAt(j)) {
            if (j != 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
}

📌 핵심 포인트

• 시간 복잡도: O(n + m)으로 매우 효율적이에요! 💡
• LPS 배열: 접두사와 접미사가 일치하는 최대 길이를 미리 계산하여 중복 검사를 방지합니다.
• 활용 사례: 텍스트 편집기 검색 기능, DNA 서열 분석 등.

---

🎯 라빈-카프 (Rabin-Karp) 알고리즘

라빈-카프 알고리즘은 문자열의 해시 값을 이용하여 패턴 매칭을 수행합니다. 해시 충돌이 발생하면 직접 문자열을 비교해 결과의 정확성을 보장합니다.

✏️ 코드

public void rabinKarp(String text, String pattern) {
    int n = text.length();
    int m = pattern.length();
    int prime = 101; // 소수
    int hashPattern = 0;
    int hashText = 0;
    int h = 1;

    for (int i = 0; i < m - 1; i++) {
        h = (h * 256) % prime;
    }

    for (int i = 0; i < m; i++) {
        hashPattern = (256 * hashPattern + pattern.charAt(i)) % prime;
        hashText = (256 * hashText + text.charAt(i)) % prime;
    }

    for (int i = 0; i <= n - m; i++) {
        if (hashPattern == hashText) {
            if (text.substring(i, i + m).equals(pattern)) {
                System.out.println("Pattern found at index: " + i);
            }
        }

        if (i < n - m) {
            hashText = (256 * (hashText - text.charAt(i) * h) + text.charAt(i + m)) % prime;
            if (hashText < 0) {
                hashText += prime;
            }
        }
    }
}

📌 핵심 포인트

• 시간 복잡도: 평균 O(n + m), 최악 O(n * m) (해시 충돌 시).
• 해시 함수: 문자열을 숫자로 변환해 비교를 빠르게 수행합니다. 🚀
• 활용 사례: 문서 검색, 플라그 감지 등.

---

2. 트라이 (Trie)

**트라이(Trie)**는 문자열 검색과 자동완성에 특화된 자료구조로, 공통 접두사를 효율적으로 저장합니다. 🌟

🎯 트라이 구현

✏️ 코드

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEndOfWord;
}

class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }
        node.isEndOfWord = true;
    }

    public boolean search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                return false;
            }
            node = node.children[index];
        }
        return node.isEndOfWord;
    }

    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                return false;
            }
            node = node.children[index];
        }
        return true;
    }
}

📌 핵심 포인트

• 시간 복잡도: 삽입, 검색 O(L) (L은 문자열 길이).
• 메모리 효율성: 공통 접두사를 재사용하여 메모리 사용량 감소.
• 활용 사례: 자동완성, 사전 검색, 문자열 집합 문제 등.

---

3. 접미사 배열과 LCP

접미사 배열은 문자열의 모든 접미사를 사전순으로 정렬한 배열입니다. LCP 배열은 접미사 배열에서 인접한 접미사 간 공통 접두사의 길이를 저장합니다. 💡

🎯 접미사 배열 생성

✏️ 코드

import java.util.Arrays;

public class SuffixArray {
    public 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, (a, b) -> a.suffix.compareTo(b.suffix));

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

    class Suffix {
        int index;
        String suffix;

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

🎯 LCP (Longest Common Prefix)

LCP 배열은 접미사 배열의 인접 원소들 간 공통 접두사의 길이를 기록하여 중복 문자열 탐색과 문자열 유사도 비교 등에 활용됩니다.

📌 핵심 포인트

• 시간 복잡도: O(n log n) (정렬 기반).
• 활용 사례: 데이터 압축, 문자열 검색, 생물정보학 등.

---

🎉 결론

문자열 알고리즘은 어렵게 느껴질 수 있지만, 체계적으로 학습하면 강력한 문제 해결 능력을 제공합니다! 💪

• KMP와 라빈-카프: 효율적인 패턴 매칭.
• 트라이: 검색과 자동완성의 강력한 도구.
• 접미사 배열과 LCP: 문자열 분석과 데이터 처리에 유용.

이제 이 알고리즘들을 활용하여 효율적이고 창의적인 프로그램을 설계해 보세요! 🌟