문제 설명

문제 분석

슈도코드

구현

public class 문자열찾기_14425 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int M = scan.nextInt();

        TNode root = new TNode();

        // 트라이 자료구조 구축
        while(N > 0) {
            String txt = scan.next();
            TNode now = root;
            for (int i = 0; i < txt.length(); i++) {
                char c = txt.charAt(i);

                // 26개 알파벳의 위치를 배열 인덱스로 나타내기 위해 -'a'
                if(now.next[c - 'a'] == null) {
                    now.next[c - 'a'] = new TNode();
                }
                now = now.next[c - 'a'];
                if(i == txt.length() - 1) {
                    now.isEnd = true;
                }
            }

            N--;
        }

        int cnt = 0;
        // 트라이 자료구조 검색
        while(M > 0) {
            String txt = scan.next();
            TNode now = root;
            for (int i = 0; i < txt.length(); i++) {
                char c = txt.charAt(i);

								// 공백 노드라면 이 문자열을 포함하지 않음
                if(now.next[c - 'a'] == null) break;

                now = now.next[c - 'a'];
                // 문자열의 끝이고 현재까지 모두 일치하면, S 집합에 포함되는 문자열임.
                if(i == txt.length() - 1 && now.isEnd) {
                    cnt++;
                }
            }

            M--;
        }

        System.out.println(cnt);
    }

    static class TNode {
        TNode[] next = new TNode[26];
        boolean isEnd; // 문자열의 마지막 유무
    }
}