Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Strings are inevitable in life. They give meaning to our expressions. Strings come in life in many ways, like a well-written letter for hearts, a nice song composed to heal the souls. For NGPC contestants like you, strings come in the form of a programming problem to give joy.

You will be given a list $\textbf{L}$ of $\textbf{N}$ strings and $\textbf{M}$ queries. The queries are of two types. They are described below:

Type 1: A prefix $P$ and a character $C$ will be given. You will have to change the $(|P| - 1)^{th}$ character to $C$ of the strings which have a prefix $P$. Note that, we start counting indexes of strings from $0$.

Type 2: A prefix $S$ will be given. You have to determine the number of strings that have a prefix that matches with $S$.

A prefix of a string $T$ is a substring of $T$ that occurs at the beginning of $T$.

The first line of the input file will contain a single positive integer $\textbf{N}$ $(1 \leq N \leq 10^{5})$ which denotes the number of strings in the list $\textbf{L}$. Each of the next $N$ lines will contain a string $\textbf{L}_{i}$ $(1 \leq |L_{i}| \leq 10^{5})$. After that, there will be a single positive integer $\textbf{M}$ $(1 \leq M \leq 10^{5})$. Each of the next $M$ lines will contain each of the two types of queries described below:

$1$ $P$ $C$

This is the first type of query. You will have to change the $(|P| - 1)^{th}$ character to $C$ of the strings which have a prefix $\textbf{Q}$ such that $Q$ $=$ $P$.

Here, $1 \leq |P| \leq 10^{5}$ and $C$ contains one of the lowercase English alphabets $(‘a’ - ‘z’)$ only.$2$ $S$

This is the second type of query. You have to determine the number of strings that have a prefix that matches with $S$.

Here, $1\leq |S| \leq 10^{5}$.

It is guaranteed that all the strings in the input file contains lowercase English alphabets $(‘a’ - ‘z’)$ only and there will be at least one query of type 2.**Other constraints:**

$1\leq \sum_{i=1}^{N} |L_{i}|\leq 3 \times 10^{6}$

$1\leq \sum |P_{i}| + \sum|S_{i}|\leq 3 \times 10^{6}$

For each of the $2^{nd}$ type of query, print the number of strings which have a prefix that matches with given prefix $S$.

Input | Output |
---|---|

2 abcdx abcex 3 1 abce d 2 abce 2 abcd | 0 2 |

75% Solution Ratio

samiulsamiEarliest,

likhon5Fastest, 0.1s

likhon5Lightest, 337 MB

serotoninShortest, 1524B

Login to submit

As we can not update all the strings that have prefix PPPfor each update query, we can hold the upda...

Toph uses cookies. By continuing you agree to our Cookie Policy.