Prefix and substring queries

4

1 votes
Algorithms, DSU, Segment Trees, String Manipulation
Problem

You are given Q queries and a string S of length N.

The queries are of the following three types: 

  • 1 c: Append character c to the end of the string S.
  • 2 xy: Consider the suffixes of equal length ending at x and y, that is, consider the substrings S[a,x], S[b,y], and xa+1=yb+1=p. Determine the maximum value of p such that S[a,x]=S[b,y]=S[1,p]. Also, determine the longest prefix S[1,p] such that the suffixes of length p ending at x and y match.
  • 3 plr: Consider the prefix of the string S[1,p]. Consider all substrings S[x,y] such that LxyR. Then, count the number of substrings S[x,y] that match with S[1,p]. In other words, S[1,p]=S[x,y].

Input format

  • First line: Two space-separated integers N and Q 
  • Second line: Single string S of length N
  • Next Q lines: Query of any of the three types provided

Output format

Print the answer for each query of type 2 and 3.

Constraints

1N1000001x,ycurrent length of string1pcurrent length of stringl+p1rcurrent length of stringa<c<z1Q200000

Note: S contains only lowercase English alphabets.

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].

Editor Image

?