Lucy and Question Marks
All submissions for this problem are available.
Read problems statements in Russian here
Long ago Lucy had written some sentences in her textbook. She had recently found those her notes. But because of the large amount of time that had passed, some letters became difficult to read. Her notes are given to you as a string with question marks in places of letters that are impossible to read.
Lucy remembers that those sentences definitely made some sense. So now she wants to restore them. She thinks that the best way to restore is to replace all the question marks by latin letters in such a way that the total sum of occurrences of all the strings from her dictionary in it is maximal. And it is normal if some word occurs in her dictionary two or more times. In this case you just have to count every word as much times as it occurs in the dictionary.
You will be given the string itself and the dictionary. Please output the maximal possible number of occurrences of dictionary words and lexicographically minimal string with this number of occurrences.
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of every test case consists of two integers N and M - the length of the string, written by Lucy and the number of words in the dictionary. The second line of the test case consists of the string itself - N characters, each is either a question mark or a small latin letter.
Then, M lines follow. Each line consist of a single string of small latin letters - the word from the dictionary.
For each test case, output a two lines. The first line should contain the maximal number of occurrences. The second line should contain lexicographically minimal string with the maximal number of occurrences of the words from the dictionary.
Input: 3 7 4 ??????? ab ba aba x 5 3 ?ac?? bacd cde xa 8 2 ?a?b?c?d ecxd zzz Output: 9 abababa 2 bacde 1 aaabecxd
Subtask 1 (16 points): T = 50, 1 <= N <= 8, 1 <= M <= 10. Only the characters a, b and c and question marks occur in the string. Only the characters a, b, and c occur in the dictionary words. All the words in the dictionary consist of no more than 10 letters.
Subtask 2 (32 points): T = 50, 1 <= N <= 100, 1 <= M <= 100. Only the characters a, b and question marks occur in the string. Only the characters a and b occur in the dictionary words. All the words in the dictionary consist of no more than 10 letters.
Subtask 3 (52 points): T = 10, 1 <= N <= 1000, 1 <= M <= 1000. Total length of all the dictionary strings will not exceed 1000.
Time limit for the last subtask equals to 2 sec. For the first two subtasks it is 1 sec.
|Tags||aho-corasick, easy-medium, ltime06, xcwgf666|
|Time Limit:||1 - 2 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