题意
给出一个母串S和m个串T，Q次询问：区间
[
L
,
R
]
[L,R]
[L,R]内，
S
[
x
,
y
]
S[x,y]
S[x,y]出现次数最多的T，并输出这个最大次数。
∣
s
∣
≤
1
e
5
,
∑
∣
T
∣
≤
5
e
4
,
q
≤
5
e
5
|s|\leq1e5,\sum|T|\leq5e4,q\leq5e5
∣s∣≤1e5,∑∣T∣≤5e4,q≤5e5
思路
考虑对单个T[i]怎么暴力做：将T跑一遍sam，然后所有在当前点fail链上，并且长度<=匹配长度的子串出现次数+1现在离线所有询问：对S建sam，倍增找到
S
[
x
,
y
]
S[x,y]
S[x,y]的点，把询问挂上去。sam上的每个点维护一颗线段树，表示
T
[
i
]
T[i]
T[i]在其"子树"内的的出现次数。每个T跑sam，将修改标记打到对应的点上。每个点按标记长度倒序修改，子树的标记线段树合并即可。
#include <bits/stdc++.h>
using namespace std
;
const int N
= 5e5 + 10;
char s
[N
], t
[N
];
int n
, tot
= 1, m
, last
= 1, link
[N
* 2], len
[N
* 2];
int c
[N
* 2][26], ed
[N
];
vector
<int> to
[N
* 2];
int extend(char r
) {
r
-= 'a';
int now
= ++tot
;
len
[now
] = len
[last
] + 1;
for(; last
&& c
[last
][r
] == 0; last
= link
[last
])
c
[last
][r
] = now
;
if (last
!= 0) {
int p
= c
[last
][r
];
if (len
[last
] + 1 == len
[p
]) {
link
[now
] = p
;
} else {
int np
= ++tot
;
len
[np
] = len
[last
] + 1;
memcpy(c
[np
], c
[p
], sizeof c
[p
]);
link
[np
] = link
[p
];
link
[p
] = link
[now
] = np
;
for(; c
[last
][r
] == p
; last
= link
[last
])
c
[last
][r
] = np
;
}
} else link
[now
] = 1;
return last
= now
;
}
int g
[N
* 2][20];
void dfs(int x
) {
for(int i
= 1; i
< 20; i
++) g
[x
][i
] = g
[g
[x
][i
- 1]][i
- 1];
for(int y
: to
[x
]) {
g
[y
][0] = x
;
dfs(y
);
}
}
pair
<int,int> ans
[N
];
struct oper
{
int len
, L
, R
, no
;
bool operator < (const oper
&b
) const {
return len
> b
.len
|| len
== b
.len
&& no
< b
.no
;
}
};
vector
<oper
> ask
[N
* 2];
int Q
;
int jump(int x
, int tg
) {
for(int i
= 19; ~i
; i
--) if (len
[g
[x
][i
]] >= tg
) {
x
= g
[x
][i
];
}
return x
;
}
namespace segment_tree
{
const int CNT
= 5e4 * 20;
int tot
, lc
[CNT
], rc
[CNT
];
pair
<int,int> mx
[CNT
];
int root
[N
* 2];
void merge(int &x
, int y
, int l
, int r
) {
if (x
== 0 || y
== 0) return void(x
= x
+ y
);
if (l
== r
) {
mx
[x
].first
+= mx
[y
].first
;
return;
}
merge(lc
[x
], lc
[y
], l
, l
+ r
>> 1);
merge(rc
[x
], rc
[y
], (l
+ r
>> 1) + 1, r
);
if (mx
[lc
[x
]].first
>= mx
[rc
[x
]].first
)
mx
[x
] = mx
[lc
[x
]];
else mx
[x
] = mx
[rc
[x
]];
}
void change(int &x
, int l
, int r
, int tg
) {
if (!x
) x
= ++tot
;
if (l
== r
) {
mx
[x
].first
++;
mx
[x
].second
= l
;
return;
}
if (tg
<= (l
+ r
>> 1)) {
change(lc
[x
], l
, l
+ r
>> 1, tg
);
} else change(rc
[x
], (l
+ r
>> 1) + 1, r
, tg
);
if (mx
[lc
[x
]].first
>= mx
[rc
[x
]].first
)
mx
[x
] = mx
[lc
[x
]];
else mx
[x
] = mx
[rc
[x
]];
}
void query(int x
, int l
, int r
, int tl
, int tr
, pair
<int,int> &w
) {
if (!x
) return;
if (tl
<= l
&& r
<= tr
) {
if (mx
[x
].first
> w
.first
) w
= mx
[x
];
return;
}
if (l
> tr
|| r
< tl
) return;
query(lc
[x
], l
, l
+ r
>> 1, tl
, tr
, w
);
query(rc
[x
], (l
+ r
>> 1) + 1, r
, tl
, tr
, w
);
}
}
void solve(int x
) {
using namespace segment_tree
;
for(int y
: to
[x
]) {
solve(y
);
merge(root
[x
], root
[y
], 1, m
);
}
sort(ask
[x
].begin(), ask
[x
].end());
for(const oper
& a
: ask
[x
]) {
if (a
.no
== 0) {
change(root
[x
], 1, m
, a
.L
);
} else {
ans
[a
.no
] = make_pair(0, a
.L
);
query(root
[x
], 1, m
, a
.L
, a
.R
, ans
[a
.no
]);
}
}
}
int main() {
freopen("e.in", "r", stdin);
scanf("%s", s
+ 1);
n
= strlen(s
+ 1);
for(int i
= 1; i
<= n
; i
++)
ed
[i
] = extend(s
[i
]);
for(int i
= 2; i
<= tot
; i
++)
to
[link
[i
]].push_back(i
);
dfs(1);
cin
>>m
;
for(int i
= 1; i
<= m
; i
++) {
scanf("%s", t
+ 1);
int lt
= strlen(t
+ 1);
int loc
= 1, mlen
= 0;
for(int j
= 1; j
<= lt
; j
++) {
int z
= t
[j
] - 'a';
while(loc
&& c
[loc
][z
] == 0)
loc
= link
[loc
], mlen
= len
[loc
];
if (loc
== 0) {
loc
= 1, mlen
= 0;
} else {
loc
= c
[loc
][z
];
mlen
++;
ask
[loc
].push_back((oper
){mlen
, i
, 0, 0});
}
}
}
cin
>>Q
;
for(int i
= 1; i
<= Q
; i
++) {
int L
, R
, x
, y
; scanf("%d %d %d %d", &L
, &R
, &x
, &y
);
int z
= jump(ed
[y
], y
- x
+ 1);
ask
[z
].push_back((oper
){y
- x
+ 1, L
, R
, i
});
}
solve(1);
for(int i
= 1; i
<= Q
; i
++)
printf("%d %d\n", ans
[i
].second
, ans
[i
].first
);
}
