Prefix and Substring Queries
Problem
You are given a string S of length N and Q queries.
The queries are of 3 types :
- 1 c : Append the character c to the end of the string S
- 2 x y : Consider the suffixes of equal length ending at x and y. i.e. consider substrings S[a, x] and S[b, y] and x - a + 1 = y - b + 1 = p. Find the maximum value of p such that S[a, x] = S[b, y] = S[1, p]. More formally, this can be stated as to find the longest prefix S[1, p] such that the suffixes of length p ending at x and y match.
- 3 p l r : Consider the prefix of the string S[1, p]. Now consider all substrings S[x, y] such that L <= x <= y <= R. Count the number of substrings S[x, y] which match with S[1, p].(i.e. S[1, p] = S[x, y]).
Input format
- First Line : Two space separated integers N and Q .
- Second Line : A single string S of length N.
- Q lines follow with each each line containing a query of any of the 3 above mentioned types.
Output format
Print the answer for each query of type 2 and 3.
Constraints
- S contains only lowercase English alphabets
- 'a' c 'z'
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation
For query 1, the suffix of length 1 ending at index 3 and 5 is the maximum length of the prefix that matches.
For query 3, only one substring matches with S[5, 6] matches with S[1, 2].
