## Mock CCC '20 S3 - SAM I Am

View as PDF

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 128M

Author:
Problem types

King Brian has recently gotten interested in manipulating strings. Today, he decided to study the Suffix Automata (SAM) data structure. However, he found it too complicated, and decided to pose this simpler problem instead:

Given an array of strings , initially filled with a single string , maintain two types of operations:

• C x_i c_i: Copy the string at and append the character to it. Then, append that new string to the back of .
• Q s_i: Given a query string , output the index of the string in that shares the longest common prefix with . If multiple strings suffice this requirement, the one with the smallest index will be the answer. Additionally, if there is no valid index, -1 is the answer.

Indices are 1-indexed.

Of course, being a king, he isn't content with answering a few measly queries. Instead, he wants you to answer of them! Are you up to the challenge?

#### Constraints

Note: for a string denotes the length of .

, all , and all will be made of lowercase English letters.

The sum of all will be .

For 3 of 15 available marks, and the sum of all will be .

#### Input Specification

The first line of input contains and .

The next lines of input contain a query of one of the types specified above.

#### Output Specification

For each query, output the answer on a new line.

#### Sample Input

chad 12
C 1 l
C 1 l
C 3 i
C 4 a
C 2 e
C 6 x
C 5 m
Q cha
Q z
Q chadliam

#### Sample Output

1
-1
2
2
8

#### Sample Explanation

After all the updates, the array of strings looks like this:

[chad, chadl, chadl, chadli, chadlia, chadle, chadlex, chadliam]