접두차찾기.java

import java.util.HashMap;
import java.util.Scanner;
import java.util.function.Function;

class Node {
  HashMap<Character, Node> child;

  public Node() {
    this.child = new HashMap<>();
  }
}

class Trie {
  Node root;

  public Trie() {
    this.root = new Node();
  }

  public void insert(String str) {
    Node cur = this.root;

    for (int i = 0; i < str.length(); i++) {
      char c = str.charAt(i);

      cur.child.putIfAbsent(c,new Node());
      cur = cur.child.get(c);
    }
  }
  public boolean search(String str){
    Node cur = this.root;

    for (int i = 0; i < str.length(); i++) {
      char c = str.charAt(i);

      if (cur.child.containsKey(c)) {
        cur = cur.child.get(c);
      }else{
        return false;
      }
    }
    return true;
  }

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

    Scanner sc = new Scanner(System.in);
    Trie trie = new Trie();
    String[] nList = sc.nextLine().split(" ");

    int n = Integer.parseInt(nList[0]);
    int k = Integer.parseInt(nList[1]);

    for (int i = 0; i < n; i++) {
      trie.insert(sc.next());
    }

    int cnt = 0;
    for (int i = 0; i < k; i++) {
      if(trie.search(sc.next())){
        cnt++;
      }
    }
    System.out.println(cnt);
  }
}