Music & Lyrics
All submissions for this problem are available.
Chef Sridhar listenes to music while cooking. He realized that the lyrics of many songs contain the same words. He thought of a task to do in his leisure; pick a set of words and find the frequency of the words in the lyrics of various songs.
A word A from the lyrics is said to match a given word W if W is a substring of A.
Note Some words from the lyrics can match multiple given words. For e.g, shawty, matches both shawty as well as hawt. The word shawty in the lyrics must be counted in the frquency of shawty as well as hawt.
You may assume that all the comparisons must be case sensitive. Also, there are no whitespaces within a word in the given list, or in the lyrics. Words in the lyrics are separated by "-" characters (of course without the quotes).
First line contains an integer W, denoting the number of words Chef has decided to find the frequencies of. Then follow W lines containing a word (P) each. The next line contains N, the number of lyrics Chef decided to index. Followed by N lines containing a string (S) which chef has to index. You can assume that S doesn't contain any whitespace characters.
The output contains W lines each denoting the frequency of the respective word in all of the lyrics together.
1 ≤ W ≤ 500
1 ≤ |P| ≤ 5000, where |P| denotes length of each word.
1 ≤ N ≤ 100
1 ≤ |S| ≤ 50000, where |S| denotes the length of lyric of each song.
All the characters will be either uppercase or lowercase english alphabets or numbers or "-".
Sample Input 1 5 he she sher his hers 2 ushers she-said-he-said-she-said-he-said-his Sample Output 1 5 3 1 1 1 Sample Input 2 3 who shawty hawt 2 Get-it-shawty-Get-it-shawty Whoa-W-W-Whoa-Shawtyyyyy Sample Output 2 0 2 3
|Tags||aho-corasick, aug13, dynamic-programming, kaushik_iska, medium-hard, string|
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.