#K451. Rearrangeable Words Count

    ID: 27678 Type: Default 1000ms 256MiB

Rearrangeable Words Count

Rearrangeable Words Count

Given a dictionary of words and a search list, your task is to determine how many words in the search list can be formed by rearranging the letters of any word from the dictionary. Two words are considered rearrangeable (anagrams) if, when their letters are sorted, they are identical.

For example, if the dictionary is ["cine", "race", "car", "act"] and the search list is ["nice", "care", "bat", "dog", "cat"], then the answer is 3 because:
- "nice" is a rearrangement of "cine"
- "care" is a rearrangement of "race"
- "cat" is a rearrangement of "act"

Mathematically, if we define a function ( sort(word) ) that returns the letters of the word in sorted order, then a word ( w ) from the search list is rearrangeable if there exists a word ( d ) in the dictionary such that ( sort(w) = sort(d) ).

inputFormat

The input is read from STDIN and consists of four lines:

1. An integer ( n ) representing the number of words in the dictionary.
2. ( n ) space-separated words representing the dictionary.
3. An integer ( m ) representing the number of words in the search list.
4. ( m ) space-separated words representing the search list.

outputFormat

Output a single integer to STDOUT which represents the number of words in the search list that can be formed by rearranging the letters of any word in the dictionary.## sample

4
cine race car act
5
nice care bat dog cat
3