记录编号 |
397696 |
评测结果 |
AAAAAAAAAAA |
题目名称 |
[HEOI 2016] 字符串 |
最终得分 |
100 |
用户昵称 |
sxysxy |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
7.241 s |
提交时间 |
2017-04-20 20:20:49 |
内存使用 |
98.82 MiB |
显示代码纯文本
#include <cstdio>
#include <cstring>
#include <cstdarg>
#include <algorithm>
#include <list>
#include <queue>
#include <deque>
#include <vector>
const int MAXN = 200020;
const int MAXD = 20;
namespace SAM{
int next[MAXN][26], link[MAXN], len[MAXN];
int last = 1, cnt = 1;
int pos[MAXN>>1];
void expand(int c, int ps){
int cur = ++cnt; len[cur] = len[last]+1, pos[ps] = cur;
int p;
for(p = last; p && !next[p][c]; p = link[p])next[p][c] = cur;
if(!p)link[cur] = 1;
else{
int q = next[p][c];
if(len[q] == len[p]+1)link[cur] = q;
else{
int clone = ++cnt; len[clone] = len[p]+1, link[clone] = link[q];
memcpy(next[clone], next[q], sizeof next[0]);
for(; p && next[p][c] == q; p = link[p])next[p][c] = clone;
link[cur] = link[q] = clone;
}
}
last = cur;
}
int dfs_tim;
int visit[MAXN], leave[MAXN];
std::vector<int> G[MAXN];
void dfs(int u){
visit[u] = ++dfs_tim;
for(int i = 0; i < G[u].size(); i++)dfs(G[u][i]);
leave[u] = dfs_tim;
}
int fa[MAXN][MAXD];
void build_tree(){
for(int i = 2; i <= cnt; i++)G[link[i]].push_back(i);
dfs(1);
for(int i = 2; i <= cnt; i++)
fa[i][0] = link[i];
for(int k = 1; 1 << k <= cnt; k++)for(int i = 1; i <= cnt; i++)
fa[i][k] = fa[fa[i][k-1]][k-1];
}
}
namespace PST{ //PersistableSegmentTree
int root[MAXN>>1];
const int MAXM = 5e6+2;
int ls[MAXM], rs[MAXM], val[MAXM], cnt;
int insert(int pre, int p, int L, int R){
int cur = ++cnt;
ls[cur] = ls[pre], rs[cur] = rs[pre], val[cur] = val[pre]+1;
if(L < R){
int M = (L+R)>>1;
if(p <= M)ls[cur] = insert(ls[cur], p, L, M);
else if(p > M)rs[cur] = insert(rs[cur], p, M+1, R);
}
return cur;
}
int query(int c, int l, int r, int L, int R){
if(!c)return 0;
if(l <= L && R <= r)return val[c];
int M = (L+R)>>1, ret = 0;
if(l <= M)ret += query(ls[c], l, r, L, M);
if(r > M)ret += query(rs[c], l, r, M+1, R);
return ret;
}
}
int n, m;
char str[MAXN>>1];
int a, b, c, d;
int find(int p, int len){
int t = SAM::pos[p];
for(int i = MAXD-1; ~i; i--){
int v = SAM::fa[t][i];
if(SAM::len[v] >= len)t = v;
}
return t;
}
bool check(int len){
int u = find(c, len);
int x = PST::query(PST::root[b-len+1], SAM::visit[u], SAM::leave[u], 1, SAM::dfs_tim);
int y = PST::query(PST::root[a-1], SAM::visit[u], SAM::leave[u], 1, SAM::dfs_tim);
return x > y;
}
int main(){
freopen("heoi2016_str.in", "r", stdin); freopen("heoi2016_str.out", "w", stdout);
scanf("%d %d", &n, &m);
scanf("%s", str+1);
for(int i = n; i; i--)SAM::expand(str[i]-'a', i);
SAM::build_tree();
for(int i = 1; i <= n; i++)
PST::root[i] = PST::insert(PST::root[i-1], SAM::visit[SAM::pos[i]], 1, SAM::dfs_tim);
while(m--){
scanf("%d %d %d %d", &a, &b, &c, &d);
int l = 0, r = std::min(b-a+1, d-c+1);
while(l < r){
int mid = l+(r-l+1)/2;
if(check(mid))l = mid; else r = mid-1;
}
printf("%d\n", l);
}
return 0;
}