## Message to Mars

View as PDF

Points: 20 (partial)
Time limit: 0.6s
Memory limit: 256M

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 made up of lowercase letters from a to z.

When King Rayregalia received the invitation, he took out his dictionary of Martian words, all different, each containing at most 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, and .
• In test cases worth another 25% of points, and .
• In test cases worth another 25% of points, .
• 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 .

The second line of input will have .

The next 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

• commented on Feb. 20, 2016, 1:12 p.m. edited

For the testcase

lelele

2

lele

le

Would the answer be 6 or 10?

• commented on Feb. 20, 2016, 2:23 p.m.

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.

• commented on Jan. 4, 2015, 1:41 p.m.

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

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

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

• commented on Jan. 4, 2015, 2:16 p.m.

thanks fatal.