069 : 문자열 찾기

(Briefing)
(문제)	(단 하나의 맥락)	(입출력과 되어야 하는 그림)
N개의 문자열로 이루어진 집합 S 입력으로 주어지는 M개의 문자열 중, S에 포함된 것이 총 몇개인지 구하는 프로그램을 작성하시오	Trie	I // 문자열 갯수 N, M (1) S에 포함된 문자열 ... (N) S에 포함된 문자열 (1) 검사해야 하는 문자열 ... (M) 검사해야 하는 문자열 O // M개의 문자열 중 총 몇개가 집합 S에 있는지 출력

*알파벳 소문자로만 이루어져 있으며, 길이는 500을 넘지 않음

*같은 문자열이 여러 번 주어지는 경우는 없다

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        // Input Supply Cable
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();

        // box recognition
        tNode root = new tNode();
        while (N > 0) {
            String text = sc.next();
            tNode now = root;
            for (int i = 0; i < text.length(); i++) {
                char c = text.charAt(i);
                if (now.next[c - 'a'] == null) {
                    now.next[c - 'a'] = new tNode();
                }
                now = now.next[c - 'a'];
                if (i == text.length() - 1)
                    now.isEnd = true;
            }
            N--;
        }
        
        // Operating Trie
        int count = 0;
        while (M > 0) {
            String text = sc.next();
            tNode now = root;
            for (int i = 0; i < text.length(); i++) {
                char c = text.charAt(i);
                if (now.next[c - 'a'] == null) {
                    break;
                }
                now = now.next[c - 'a'];
                if (i == text.length() - 1 && now.isEnd)
                    count++;
            }
            M--;
        }
        
        // Output Extracting Cable
        System.out.println(count);
    }
}

// External Class tNode
class tNode {
    tNode[] next = new tNode[26];
    boolean isEnd;
}