백준 9250번 : 문자열 집합 판별 - 아호코라식 Java

https://www.acmicpc.net/problem/9250

9250번: 문자열 집합 판별

 

 

//package org.example;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
    final int MX = 26;
 
    class Trie {
        Trie child[];
        Trie fail;
        boolean output;
 
        public Trie() {
            child = new Trie[MX];
            Arrays.fill(child, null);
        }
 
        void insert(String str) {
            Trie tmp = this;
            for (int i = 0; i < str.length(); i++) {
                int cur = str.charAt(i) - 'a';
 
                if (tmp.child[cur] == null) {
                    tmp.child[cur] = new Trie();
                }
                tmp = tmp.child[cur];
            }
            tmp.output = true;
        }
 
        boolean check(String str) {
            Trie tmp = this;
 
            for (int i = 0; i < str.length(); i++) {
                int next = str.charAt(i) - 'a';
 
                while(tmp!= this && tmp.child[next] == null){
                    tmp = tmp.fail;
                }
                if(tmp.child[next]!=null){
                    tmp = tmp.child[next];
                }
                if(tmp.output){
                    return true;
                }
            }
 
            return false;
        }
 
        void computeFailFunc(){
            Queue<Trie> q = new LinkedList<>();
            Trie root = this;
            root.fail = this;
            q.add(root);
 
            while(!q.isEmpty()){
                Trie here = q.poll();
 
                for(int edge = 0; edge<MX; edge++){
                    Trie child = here.child[edge];
                    if(child == null) continue;
 
                    if(here == root) child.fail = root;
                    else{
                        Trie t = here.fail;
 
                        while(t!=root && t.child[edge] == null){
                            t = t.fail;
                        }
 
                        if(t.child[edge] != null) t = t.child[edge];
                        child.fail = t;
                    }
 
                    if(child.fail.output) child.output = true;
                    q.add(child);
                }
            }
        }
    }
 
    public void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
 
        Trie root = new Trie();
 
        int N = Integer.parseInt(br.readLine());
        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            root.insert(str);
        }
 
        root.computeFailFunc();
 
        int M = Integer.parseInt(br.readLine());
        for (int i = 0; i < M; i++) {
            String str = br.readLine();
            if (root.check(str)) sb.append("YES\n");
            else sb.append("NO\n");
        }
        System.out.println(sb);
    }
 
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}