STRLCP - Longest Common Prefix

no tags 

The LCP (Longest Common Prefix) of two strings A[1..la] and B[1..lb] is defined as follows:

LCP(A[1..la],B[1..lb]) = max{L | L<=la && L<=lb && A[1..L] == B[1..L]}

Given an original string and several operations, you should write a program to process all the operations.

Input

The first line will be number of test cases T.
The first line of each test case is a string S with length L (1 <= L <= 100000).
The second line contains an integer Q(1 <= Q <= 150000), representing the number of operations.

Each of the following Q lines represents an operation:
Q i j: print LCP(S[i..L], S[j..L])
R i char: replace the i-th character of S with char
I i char: insert character char after the i-th character of S

Output

For each "Q i j" operation, print the answer.

Example

Input:
1
madamimadam
7
Q 1 7
Q 4 8
Q 10 11
R 3 a
Q 1 7
I 10 a
Q 2 11

Output:
5
1
0
2
1

hide comments
DK...: 2019-05-22 03:27:48

O(nlog(n)+qlog^2(n)) is enough!

oscar172772: 2017-12-25 15:38:30

1AC. similar problem:www.lydsy.com/JudgeOnline/problem.php?id=1014 (Chinese version?)

Last edit: 2017-12-25 15:39:07
Allada Revanth Kumar: 2012-02-02 04:05:27

i j will be <= L & >=1 ??

Last edit: 2012-02-02 05:32:41
Allada Revanth Kumar: 2012-02-02 04:02:31

Uffh... 5 SIGABRTs, 4 RE, 3 TLE, 2 CE.... finally AC :)

Last edit: 2012-02-02 05:47:58
iT@cHi: 2012-01-02 14:24:19

It took me many incorrect submissions before realizing that the insert operation is done after the ith character :-P

_|_: 2011-12-15 05:24:53

Dont hav any space in string ......no need to use getline.....caused too many problems......finally ac...

Aman Kumar: 2011-12-14 12:53:18

same here ! got loads of (SIGSEGV) ..... i ws using character array.....changed everything to strings...finally got AC :))

MR. BEAN : 2011-10-15 21:08:12

6 RE :):):)
finally got AC....

Last edit: 2011-12-14 12:32:30

Added by:eleusive
Date:2008-10-04
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Al-Khawarizm 2008