STRLCP - Longest Common Prefix
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
littlemomol:
2022-09-29 15:37:27
RE ans TLE, I am dead... |
|
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 :):):)
|
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 |