1
import java.util.HashMap;
2
import java.util.Map;
3

4
/**
5
 * 트라이의 개별 노드를 나타내는 클래스
6
 */
7
class TrieNode {
8

9
    /**
10
     * 자식 노드들을 저장하는 맵
11
     * key: 문자 (Character)
12
     * value: 해당 문자에 해당하는 자식 노드 (TrieNode)
13
     */
14
    private final Map<Character, TrieNode> children = new HashMap<>();
15

16
    /**
17
     * 이 노드에서 끝나는 단어가 있는지 여부를 표시하는 깃발
18
     */
19
    private boolean isEndOfWord;
20

21
    Map<Character, TrieNode> getChildren() {
22
        return children;
23
    }
24

25
    boolean isEndOfWord() {
26
        return isEndOfWord;
27
    }
28

29
    void setEndOfWord(boolean endOfWord) {
30
        isEndOfWord = endOfWord;
31
    }
32
}
33

34
/**
35
 * 트라이 (Trie) 자료구조 클래스
36
 */
37
public class Trie {
38

39
    private final TrieNode root;
40

41
    /**
42
     * Trie 생성자. 루트 노드를 초기화
43
     */
44
    public Trie() {
45
        root = new TrieNode();
46
    }
47

48
    /**
49
     * 트라이에 새로운 단어를 삽입
50
     * 시간 복잡도: O(L) - L은 단어의 길이
51
     *
52
     * @param word 삽입할 단어
53
     */
54
    public void insert(String word) {
55
        TrieNode current = root;
56

57
        for (char ch : word.toCharArray()) {
58
            current = current.getChildren()
59
                             .computeIfAbsent(ch, c -> new TrieNode());
60
        }
61

62
        current.setEndOfWord(true);
63
    }
64

65
    /**
66
     * 트라이에서 특정 단어가 '완전히' 일치하는지 검색
67
     * 시간 복잡도: O(L) - L은 단어의 길이
68
     *
69
     * @param word 검색할 단어
70
     * @return 단어가 존재하고, 해당 노드가 '단어의 끝'이면 true, 아니면 false
71
     */
72
    public boolean search(String word) {
73

74
        TrieNode node = findNode(word);
75

76
        return node != null && node.isEndOfWord();
77
    }
78

79
    /**
80
     * 트라이에서 특정 '접두사'로 시작하는 단어가 있는지 검색
81
     * 시간 복잡도: O(L) - L은 접두사의 길이
82
     *
83
     * @param prefix 검색할 접두사
84
     * @return 접두사에 해당하는 노드 경로가 존재하면 true, 아니면 false
85
     */
86
    public boolean startsWith(String prefix) {
87
        return findNode(prefix) != null;
88
    }
89

90
    /**
91
     * 문자열을 따라 트라이를 탐색하여 마지막 노드를 찾는 내부 헬퍼 메서드
92
     *
93
     * @param str 검색할 문자열 (단어 또는 접두사)
94
     * @return 문자열의 마지막 문자에 해당하는 노드. 경로가 없으면 null 반환
95
     */
96
    private TrieNode findNode(String str) {
97
        TrieNode current = root;
98
        for (char ch : str.toCharArray()) {
99
            TrieNode node = current.getChildren().get(ch);
100

101
            if (node == null) {
102
                return null;
103
            }
104
            current = node;
105
        }
106
        return current;
107
    }
108

109
    public static void main(String[] args) {
110
        Trie trie = new Trie();
111

112
        // 1. 삽입
113
        trie.insert("apple");
114
        trie.insert("apply");
115
        trie.insert("banana");
116
        trie.insert("bat");
117

118
        // 2. 검색
119
        System.out.println("trie.search(\"apple\"): " + trie.search("apple"));   // true
120
        System.out.println("trie.search(\"app\"): " + trie.search("app"));     // false ("app" 자체는 삽입 안 함)
121
        System.out.println("trie.search(\"apply\"): " + trie.search("apply"));   // true
122
        System.out.println("trie.search(\"batman\"): " + trie.search("batman")); // false
123

124
        // 3. 접두사 검색
125
        System.out.println("trie.startsWith(\"app\"): " + trie.startsWith("app"));   // true ("apple", "apply")
126
        System.out.println("trie.startsWith(\"ban\"): " + trie.startsWith("ban"));   // true ("banana")
127
        System.out.println("trie.startsWith(\"cat\"): " + trie.startsWith("cat"));   // false
128
    }
129
}

1
import java.util.ArrayList;
2
import java.util.List;
3

4
public class KMP {
5

6
    /**
7
     * KMP의 핵심인 'pi' 배열 (실패 함수)을 생성
8
     * pi[i] = pattern[0...i]의 접두사==접미사 최대 길이
9
     *
10
     * @param pattern 검색할 패턴 문자열
11
     * @return 계산된 pi 배열
12
     */
13
    private int[] getPi(String pattern) {
14
        int m = pattern.length();
15
        int[] pi = new int[m];
16

17
        int j = 0;
18

19
        for (int i = 1; i < m; i++) {
20
            while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
21
                j = pi[j - 1];
22
            }
23

24
            if (pattern.charAt(i) == pattern.charAt(j)) {
25
                pi[i] = ++j;
26
            }
27
        }
28
        return pi;
29
    }
30

31
    /**
32
     * KMP 알고리즘을 사용해 텍스트에서 패턴을 검색
33
     *
34
     * @param text    전체 텍스트
35
     * @param pattern 찾을 패턴
36
     * @return 패턴이 시작되는 모든 인덱스의 리스트
37
     */
38
    public List<Integer> search(String text, String pattern) {
39
        List<Integer> foundIndices = new ArrayList<>();
40
        int[] pi = getPi(pattern);
41

42
        int n = text.length();
43
        int m = pattern.length();
44

45
        int j = 0;
46

47
        for (int i = 0; i < n; i++) {
48
            while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
49
                j = pi[j - 1];
50
            }
51

52
            if (text.charAt(i) == pattern.charAt(j)) {
53
                if (j == m - 1) {
54
                    foundIndices.add(i - m + 1);
55
                    j = pi[j];
56
                } else {
57
                    j++;
58
                }
59
            }
60
        }
61
        return foundIndices;
62
    }
63

64
    public static void main(String[] args) {
65
        KMP kmp = new KMP();
66
        String text = "ABABCABABCDA";
67
        String pattern = "ABABC";
68

69
        List<Integer> result = kmp.search(text, pattern);
70
        System.out.println("패턴 발견 위치: " + result); // [0, 5]
71

72
        text = "AAAAABAAABA";
73
        pattern = "AAAA";
74
        result = kmp.search(text, pattern);
75
        System.out.println("패턴 발견 위치: " + result); // [0, 1, 7]
76
    }
77
}

1
- 시간 복잡도: O(L)
2
- `Trie` 생성(O(L)) + `Failure Link` 생성 (O(L))
3
- 서버 시작 시 최초 1회 수행

1
- 시간 복잡도: O(N + M)
2
- 텍스트 포인터는 KMP처럼 뒤로가지 않고 N번 전진함. 실패 링크를 따라 점프하는 횟수는 텍스트 전진 횟수를 넘을 수 없음
3
- M은 발견된 결과를 기록하는 시간