Lost in strings

3.7

43 votes
Algorithms, Data Structures, Graphs, String Manipulation, Tries
Problem

You have a list in which you store strings. The list is indexed from 1. Initially, the list contains only one string S.

There are three different types of tasks that you are asked to perform:

1pnc: Create a new string of length p using the nth string from the list such that all characters from 1 to p1 in the new string are the same as in the old string and the pth character is c. Append this string to the end of the list.

2pn: Create a new string of length p using the nth string from the list such that all the characters from 1 to p in the new string are the same as in the old string. Append this string to the end of the list.

3lrs: Print yes if string s appears as the prefix of any string in the range [l,r] of the list, else print no.

Input format

  • First line: String S represents the only string that is initially in the list
  • Next line: Q represents the number of queries to be performed
  • Next Q lines: Each line describes one of the three types of tasks that can be performed. All the tasks are valid.

Output format

For every task of type 3, print yes or no.

Constraints

|S|105

Q3105

Constraints that apply to all the queries

For the query to perform the task of type 10p1|sizeofnthstring|

For the query to perform the task 21p<|sizeofnthstring|

1n|currentsizeoflist|

c[a,b], i.e. all the characters are lowercase English alphabets

1lr|currentsizeoflist|

Q|si|106

sisj if ij, for all the strings in the list. i.e. all the strings in the list are unique

c[a,z] (not[a,b])

Sample Input
apple
5
1 2 1 x
1 3 2 e
2 3 1
3 2 4 ap
3 1 3 aye
Sample Output
yes
no
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

Initially, the list is [apple]

In first query, a task of type 1 is performed. A new string 'ax' is made and appended at end of list. The list becomes[apple,ax]

In second query, again a task of type 1 is performed. This time, the new string formed is 'axe'. The list now becomes [apple,ax,axe]

In third query, a task of type 2 is performed. The new string 'app' is formed using the first 3 characters of 1st string i.e.'apple'. The list now becomes [apple,ax,axe,app]

In fourth query, since 'ap' exists as prefix of string 'app', and index of 'app' being 4, it lies in range [2,4], print yes.

In fifth query, since 'aye' doesn't exists as prefix of any string in range [1,3] of list. print no.

 

Editor Image

?