New Year's '15 P5 - Message to Mars

View as PDF
Submit solution
Points: 20 (partial)
Time limit: 0.6s
Memory limit: 256M
Author:
FatalEagle
Problem types

Princess Asseylum Vers Allusia needs to send a party invitation to her father, King Rayregalia Vers Rayvers on Mars! However, she cannot send the invitation in plain text, because enemies are intercepting messages at the moon base. Therefore, Princess Asseylum decided to encrypt her message by concatenating all of the Martian words in her message together to form one long string. The encrypted message is a string S (1 \le |S| \le 2\,000) made up of lowercase letters from a to z.

When King Rayregalia received the invitation, he took out his dictionary of N (1 \le N \le 2\,000) Martian words, all different, each containing at most 2\,000 lowercase letters from a to z. Unfortunately, King Rayregalia is getting old, and in his bedridden state he is unable to understand what his daughter is trying to convey because when he looks at the invitation, all he can think about is that the substrings of it look like they also contain important information! A substring is important if and only if it is created by concatenating one or more Martian words together (repeats are allowed). Since there are an overwhelming number of substrings for King Rayregalia to check manually, he has hired you to advise him on the number of important substrings of Princess Asseylum's invitation.

Constraints

  • In test cases worth 25% of points, 1 \le |S| \le 50 and 1 \le N \le 7.
  • In test cases worth another 25% of points, 1 \le |S| \le 100 and 1 \le N \le 100.
  • In test cases worth another 25% of points, 1 \le |S| \le 500.
  • In the rest of the test cases, the constraints given in the problem statement will hold.

Input Specification

The first line of input will have S.

The second line of input will have N.

The next N lines of input will each have a word in King Rayregalia's dictionary.

Output Specification

A single line containing the number of important substrings.

Sample Input 1

dearfather
2
dear
father

Sample Output 1

3

Sample Input 2

iamwritingfromearthtoinformyouofmysituation
7
a
i
my
to
of
it
earth

Sample Output 2

22

Sample Input 3

itspartytime
3
its
party
time

Sample Output 3

6

Comments


  • 6
    kobortor  commented on Feb. 20, 2016, 6:12 p.m. ← edited

    For the testcase

    lelele

2

lele

le

    Would the answer be 6 or 10?


    • 6
      bruce  commented on Feb. 20, 2016, 7:23 p.m.

      The answer is 6.

      A substring is important if and only if it is created by concatenating one or more Martian words together (repeats are allowed).

      In your case, there are 3 important substrings "le", 2 important substrings "lele", and 1 important substring "lelele". So, the answer is 3+2+1=6.

      If a substring is important, it doesn't matter to decompose it as key words A+B or C+D.


  • 3
    omaewamoushindeiru  commented on Jan. 4, 2015, 6:41 p.m.

    could someone provide an input/output explanation for any example test case?


    • 6
      FatalEagle  commented on Jan. 4, 2015, 6:43 p.m.

      Case 1: The three important substrings are dear, father, dearfather.