EPIC1307 - Subwords

no tags 

Subwords is a game wherein you are given a word and must find all possible rearrangements of the letters that form English words.  Not all letters need be used.  For example, if you're given the word "computer" then four possible subwords are:

  • Court
  • Outer
  • Truce
  • Pure

Given an input word and a list of dictionary words, return the total number of valid subwords found.

Note that a word is not considered a subword of itself.  For example, with the input "computer" if you find "computer" in the dictionary then it should not be counted.

Additionally, a subword should not be counted twice if there are multiple ways to form that word.  For example, if your word is balloon then you should not count the word "on" twice using each 'o'.  It should be counted only once.

Input

The first string input is the starting word.  All remaining strings are the dictionary.  You should ignore any blank lines.  Note that you may need to be able to handle a long list of words (tens of thousands).

Output

The number of subwords found in the dictionary.

Example

Input:
computer
aardvark
computer
court
outer
pure
truce
wish
Output:
4

hide comments
nadstratosfer: 2018-06-26 05:54:43

Words contain uppercase characters and punctuation.


Added by:BYU Admin
Date:2013-03-20
Time limit:2s-10s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64