1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
|
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
const int maxn = 1e5;
ull h[maxn];
ull bin[maxn];
const int base = 131;
char s[maxn];
int pos[maxn];
int n, m;
void (){
h[0] = 0;
bin[0] = 1;
n = strlen(s + 1);
for(int i = 1; i <= n; i++)h[i] = h[i - 1] * base + s[i];
for(int i = 1; i < maxn; i++)bin[i] = bin[i - 1] * base, pos[i] = i;
}
void change(char c, int x){
for(int i = n + 1; i > x; i--)s[i] = s[i - 1];
s[x] = c;
n++;
for(int i = x; i <= n; i++)h[i] = h[i - 1] * base + s[i];
for(int i = n; i >= 1; i--)if(pos[i] >= x)pos[i]++;
else break;
}
ull get(int l, int r){
return h[r] - h[l - 1] * bin[r - l + 1];
}
int solve(int l, int r){
if(l > r)swap(l, r);
int lb = 0;
int ub = n - r + 1;
int ans = 0;
while(ub >= lb){
int mid = ub + lb >> 1;
if(get(l, l + mid - 1) == get(r, r + mid - 1)){
ans = max(ans, mid);
lb = mid + 1;
}
else ub = mid - 1;
}
return ans;
}
int main(){
scanf("%s", s + 1);
init();
scanf("%d", &m);
while(m--){
char ch[2];
scanf("%s", ch);
if(ch[0] == 'Q'){
int l, r;
scanf("%d %d", &l, &r);
printf("%dn", solve(pos[l], pos[r]));
}
else{
char c[2];
int a;
scanf("%s %d", c, &a);
if(a > n) a = n + 1;
change(c[0], a);
}
}
return 0;
}
|
近期评论