| 22 | |
| 23 | // Step 2: Build Failure Links |
| 24 | public void buildFailureLinks() { |
| 25 | Queue<TrieNode> queue = new LinkedList<>(); |
| 26 | root.failureLink = root; |
| 27 | queue.add(root); |
| 28 | |
| 29 | while (!queue.isEmpty()) { |
| 30 | TrieNode current = queue.poll(); |
| 31 | |
| 32 | for (Map.Entry<Character, TrieNode> entry : current.children.entrySet()) { |
| 33 | char c = entry.getKey(); |
| 34 | TrieNode child = entry.getValue(); |
| 35 | |
| 36 | // Set failure link |
| 37 | TrieNode failure = current.failureLink; |
| 38 | while (failure != root && !failure.children.containsKey(c)) { |
| 39 | failure = failure.failureLink; |
| 40 | } |
| 41 | |
| 42 | if (failure.children.containsKey(c) && failure.children.get(c) != child) { |
| 43 | child.failureLink = failure.children.get(c); |
| 44 | } else { |
| 45 | child.failureLink = root; |
| 46 | } |
| 47 | |
| 48 | // Merge output from failure link |
| 49 | child.output.addAll(child.failureLink.output); |
| 50 | queue.add(child); |
| 51 | } |
| 52 | } |
| 53 | } |
| 54 | |
| 55 | // Step 3: Search the Text |
| 56 | public List<String> search(String text) { |