Mock CCC '20 S3 - SAM I Am

View as PDF

Submit solution

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

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 A, initially filled with a single string S, maintain two types of operations:

  • C x_i c_i: Copy the string at A_{x_i} and append the character c_i to it. Then, append that new string to the back of A.
  • Q s_i: Given a query string s_i, output the index of the string in A that shares the longest common prefix with s. 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 Q of them! Are you up to the challenge?


Note: |x| for a string x denotes the length of x.

For all subtasks:

1 \le |S|, Q \le 10^5

1 \le |s_i| \le 4 \times 10^5

S, all s_i, and all c_i will be made of lowercase English letters.

The sum of all |s_i| will be \le 2 \times 10^6.

For 3 of 15 available marks, 1 \le Q, |S| \le 100 and the sum of all |s_i| will be \le 400.

Input Specification

The first line of input contains S and Q.

The next Q 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 chadl
Q chadlliam
Q chadliam

Sample Output


Sample Explanation

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

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


There are no comments at the moment.