根据字典序的定义,位置大的大于长度长的,长度长的大于长度短的。
所以我们贪心,先追求长度长的,再追求后面的位置大的,再追求前面的位置大的。
我们要一个能遍历子串的结构,就选 SAM 得了。
还有个限制:为 S[L...R] 的字串。正好 SAM 有个东西叫做 endpos,用线段树合并求一下就求出来了。
注意当当前字符串长度为 \(len\) 时,endpos 要有 S[L+len...R] 才行。因为 endpos统计的是结尾。
再提一嘴,要一直保证 endpos 的条件成立,不行就退出。否则会超时。
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define mp make_pair
#define forp(i, a, b) for(int i = (a);i <= (b);i ++)
using namespace std;
const int maxn = 2e7 + 5;
int n;
string T;int L, R;
namespace linetree
{
int ch[8000005][2], rt[200005], tot;
void make(int p, int i)
{
rt[p] = ++ tot;int u = rt[p], l = 1, r = n;
while(1)
{
int mid = l + r >> 1;
if(l == r) break;
(mid >= i) ? (r = mid, u = ch[u][0] = ++ tot) : (l = mid + 1, u = ch[u][1] = ++ tot);
}
// cout << l << ' ' << r << ' ' << i << ' ' << u << endl;
}
int merge(int u, int v, int len) {
if (!u || !v) return u += v;
int p = ++ tot;
if (len != 1) ch[p][0] = merge(ch[u][0], ch[v][0], len + 1 >> 1), ch[p][1] = merge(ch[u][1], ch[v][1], len >> 1);
return p;
}
int query(int p, int l, int r, int fl, int fr)
{
if(fl <= l && fr >= r) return 1;
int mid = l + r >> 1, ans = 0;
if(fl <= mid && ch[p][0]) ans |= query(ch[p][0], l, mid, fl, fr);
if(fr >= mid + 1 && ch[p][1]) ans |= query(ch[p][1], mid + 1, r, fl, fr);
return ans;
}
}
int c[100005], fin;
namespace SAM
{
struct point{ int ch[26], fa, len; }a[200005];
int las = 1, tot = 1;
ll f[200005];
void add(int s, int i)
{
int p = las, np = las = ++ tot;f[np] = 1;
linetree::make(np, i);
a[np].len = a[p].len + 1;
for(;p && a[p].ch[s] == 0;p = a[p].fa) a[p].ch[s] = np;
if(p == 0){ a[np].fa = 1; return ; }
int q = a[p].ch[s];
if(a[q].len == a[p].len + 1){ a[np].fa = q; return ; }
int nq = ++ tot;a[nq] = a[q];
a[q].fa = a[np].fa = nq;
a[nq].len = a[p].len + 1;
for(;p && a[p].ch[s] == q;p = a[p].fa) a[p].ch[s] = nq;
}
bool run(int i, int u, int pd)
{
if(u == 0) return 0;
if(linetree::query(linetree::rt[u], 1, n, L + (i - 1) - 1, R) == 0) return 0;
if(pd == 1) return 1;
if(i == T.size() + 1)
{
forp(j, 0, 25){ c[i] = j; if(run(i + 1, a[u].ch[j], 1)){ fin = i; return 1; } }
return 0;
}
c[i] = T[i - 1] - 'a'; if(run(i + 1, a[u].ch[T[i - 1] - 'a'], 0)) return 1;
forp(j, T[i - 1] - 'a' + 1, 25){ c[i] = j; if(run(i + 1, a[u].ch[j], 1)){fin = i; return 1;} }
return 0;
}
vector<int> e[200005];
void init(){ forp(i, 2, tot) e[a[i].fa].push_back(i); }
void build(int u)
{
for(auto v : e[u])
{
build(v);
linetree::rt[u] = linetree::merge(linetree::rt[u], linetree::rt[v], n);
}
}
}
signed main()
{
freopen("text.in", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
string s;
cin >> s;
n = s.size();
forp(i, 1, s.size()) SAM::add(s[i - 1] - 'a', i);
SAM::init();SAM::build(1);
int q;
cin >> q;
// cout << "#### " << linetree::query(linetree::rt[4], 1, n, 3, 3) << endl;
while(q --)
{
cin >> L >> R >> T;
if(SAM::run(1, 1, 0))
{
// if(c[3] == 'm' - 'a' && c[2] == 'y' - 'a' && c[1] == 'o' - 'a' && fin == 3) cout << "#### " << T << endl;
forp(i, 1, fin) cout << char(c[i] + 'a');
cout << endl;
}
else cout << -1 << endl;
}
return 0;
}
标签:ch,return,fa,int,题解,len,CF1037H,np,Security
From: https://www.cnblogs.com/closureshop/p/17085909.html