PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Sourav Biswas
Testers: Satyam, Jatin Garg
Editorialist: Nishank Suresh
DIFFICULTY:
2745
PREREQUISITES:
Palindromic tree/Manacher’s algorithm (or hashing), string suffix structures (or hashing), binary search
PROBLEM:
You have a string S. Form a new string T by taking all the distinct palindromic substrings of S, sorting them lexicographically, and then concatenating them in this order into a single large string.
Now you have Q queries, each of the form L, R. Given a query, you need to print the substring of T that starts at position L and ends at position R, or say that such a substring doesn’t exist (i.e R is larger than the size of T)
EXPLANATION:
The solution can be broken into 3 parts: finding all the distinct palindromes of S, sorting them, and finally answering queries.
Finding palindromes
It so happens that there is a data structure that finds all distinct palindromic substrings of a string and keeps information about them in linear time, called the palindromic tree. You can read about it here or here.
However, knowledge of this data structure isn’t strictly needed to solve the problem: you can apply some other well-known algorithms as well.
The most important property of palindromic substrings is that there are at most N of them.
Proof
This can be proved by induction on the length of the string.
When N = 1, clearly there is only one palindromic substring.
Now, consider what happens when you append a character to a string of length N to form one of length N+1 how many new palindromes are created?
Clearly any new palindrome must end at the last character, so consider all palindromes ending at the last character.
Only the largest one of these is a potentially new palindrome: all the shorter ones will also appear as a prefix of the longest one (since they form a suffix of it), and thus already exist within the first N characters.
Adding a new character adds at most one new palindromic substring. So, a string with N characters has at most N distinct palindromic substrings.
The above proof also gives us an idea to compute these N substrings: each of them must be the longest palindrome ending at some index of the string, so we just need to be able to compute this.
This can be done with the help of Manacher’s algorithm.
Manacher computes, for each index i, the (half-length of the) longest palindrome centered at i. Suppose this length is k. Then, the longest palindrome ending at i+j for each i \leq i+j \leq i+k has length at least j+1.
There are 2N-1 restrictions of this form (N from the odd lengths, N-1 from the even lengths). Then, the actual length of the longest palindrome ending at each position can be computed from this using a sweep line.
Finding these lengths can also be done with a combination of hashing and binary search. You can read about it here.
This part takes \mathcal{O}(N) or \mathcal{O}(N\log N), depending on implementation and method chosen.
Sorting the palindromes
Now that we have found our \leq N distinct palindromes, we need to sort them lexicographically.
This is a more general problem of sorting several substrings of a string, and can be accomplished in several ways:
- Build the suffix array of the string, which automatically gives us this information; or
- Once again, use hashing and binary search — this time, to compare two substrings in \mathcal{O}(\log N) time and use a standard sorting algorithm for an \mathcal{O}(N\log ^2 N) implementation. You can read about the details of this here.
Depending on the method chosen, this step is \mathcal{O}(N), \mathcal{O}(N\log N), or \mathcal{O}(N\log^2 N).
Also note that depending on implementation, you might have duplicate palindromes at this stage. After sorting them, make sure to remove duplicates or it’ll mess up the next step.
Answering queries
Now that the substrings have been sorted, answering queries is fairly easy.
Let the length of the i-th palindrome be len_i.
Given a query [L, R]:
- if R is larger then the sum of all len_i, print -1
- Otherwise, find the first index i such that len_1 + len_2 + \ldots + len_i \geq L. This can be done with binary search on the prefix sums of len_i.
Position L of T is then in the i-th substring, and its index can be found easily. - Now, simply start printing characters from L till you reach R, each time moving to the next palindrome when you reach the end of one.
The complexity of answering a single query is \mathcal{O}(\log N + len(output)). Since we are guaranteed that the sum of output lengths across all queries is bounded, this is good enough.
TIME COMPLEXITY
\mathcal{O}((N+Q)\log N) per test case (with maybe an extra \log N if hashing is used).
CODE:
Setter's code (Paltree + hashing) (C++)
#pragma GCC diagnostic ignored "-Wunused-variable"
#pragma GCC diagnostic ignored "-Wunused-parameter"
#pragma GCC diagnostic ignored "-Wunused-but-set-variable"
#pragma GCC diagnostic ignored "-Wformat"
#pragma GCC diagnostic ignored "-Wsign-compare"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N = 2e5 + 4;
const ll P = 233;
const int A = 26;
const int MOD = 1e9 + 123;
ll h[N], pwr[N], inv[N];
vector<ll> prefix_sum;
map<ll, ll> M;
int n, q; ll l, r;
char s[200005];
int tree[N][26], idx;
int len[N], link[N], t;
//------------ Hash code Starts
ll bigMod (ll a, ll e) {
if (e == -1) e = MOD - 2;
ll ret = 1;
while (e) {
if (e & 1) ret = ret * a % MOD;
a = a * a % MOD, e >>= 1;
}
return ret;
}
void init_hash(){
pwr[0] = inv[0] = 1;
ll INV_P = bigMod(P, -1);
for (int i = 1; i < N; ++i) {
pwr[i] = pwr[i - 1] * P % MOD;
inv[i] = inv[i - 1] * INV_P % MOD;
}
}
void build_hash(){
for (int i = 1; i <= n; ++i) {
h[i] = (h[i - 1] + (s[i] - 'a' + 1) * pwr[i]) % MOD;
}
}
ll get_hash(int l, int r){
ll one = (h[r] - h[l - 1]) * inv[l] % MOD;
if (one < 0) one += MOD;
return one;
}
// -------------------Hash code ends
struct struct_pair{
int idx, len;
struct_pair(){}
struct_pair(int a, int b){
idx = a; len = b;
}
bool operator<(struct_pair other)const{
int mx = min(len, other.len); mx--;
int lo = 0, hi = mx, mid;
while(lo <= hi){
mid = (lo + hi) / 2;
if(get_hash(idx, idx + mid) == get_hash(other.idx,other.idx + mid))lo = mid + 1;
else hi = mid - 1;
}
if(lo == mx + 1)return len < other.len; // emon case aabaa aabaabaa
return s[idx + lo] < s[other.idx + lo];
}
};
vector<struct_pair> vsp;
//------------Palindromic Tree Starts
void extend(int p) {
while(s[p - len[t] - 1] != s[p]) t = link[t];
int x = link[t], c = s[p] - 'a';
while(s[p - len[x] - 1] != s[p]) x = link[x];
if(!tree[t][c]) {
tree[t][c] = ++idx;
len[idx] = len[t] + 2;
link[idx] = len[idx] == 1 ? 2 : tree[x][c];
vsp.push_back(struct_pair(p - len[idx] + 1, len[idx]));
} t = tree[t][c];
}
//------------Palindromic Tree Ends.
int main(){
scanf("%d", &n);
scanf("%s", s + 1);
len[1] = -1; link[1] = 1;
len[2] = 0; link[2] = 1;
idx = t = 2;
for(int i = 1; i <= n; i++) extend(i);
init_hash();
build_hash();
sort(vsp.begin(), vsp.end());
int distpal = vsp.size();
ll sum = 0;
for(int i = 0; i < distpal; i++){
sum += vsp[i].len;
prefix_sum.pb(sum);
M[sum] = i + 1;
}
scanf("%d", &q);
for(int cs = 1; cs <= q; cs++){
scanf("%lld %lld", &l, &r);
int idxl = lower_bound(prefix_sum.begin(), prefix_sum.end(), l) - prefix_sum.begin();
auto idxr = lower_bound(prefix_sum.begin(), prefix_sum.end(), r);
if(idxr == prefix_sum.end()){
printf("-1\n"); continue;
}
ll prevsum = 0;
if(idxl)prevsum = prefix_sum[idxl - 1];
int idx = vsp[idxl].idx + (l - prevsum) - 1;
while(l <= r){
printf("%c", s[idx]);
idx++;
if(M.find(l) != M.end())idx = vsp[M[l]].idx;
l++;
}
printf("\n");
}
}
Tester (rivalq)'s code (Paltree + suffix array) (C++)
// Jai Shree Ram
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define ll long long
#define int long long
#define pb push_back
#define all(v) v.begin(),v.end()
#define endl "\n"
#define x first
#define y second
#define gcd(a,b) __gcd(a,b)
#define mem1(a) memset(a,-1,sizeof(a))
#define mem0(a) memset(a,0,sizeof(a))
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define hell 1000000007
#define elasped_time 1.0 * clock() / CLOCKS_PER_SEC
template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.x>>a.y;return in;}
template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.x<<" "<<a.y;return out;}
template<typename T,typename T1>T maxs(T &a,T1 b){if(b>a)a=b;return a;}
template<typename T,typename T1>T mins(T &a,T1 b){if(b<a)a=b;return a;}
// -------------------- Input Checker Start --------------------
long long readInt(long long l, long long r, char endd)
{
long long x = 0;
int cnt = 0, fi = -1;
bool is_neg = false;
while(true)
{
char g = getchar();
if(g == '-')
{
assert(fi == -1);
is_neg = true;
continue;
}
if('0' <= g && g <= '9')
{
x *= 10;
x += g - '0';
if(cnt == 0)
fi = g - '0';
cnt++;
assert(fi != 0 || cnt == 1);
assert(fi != 0 || is_neg == false);
assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
}
else if(g == endd)
{
if(is_neg)
x = -x;
if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(false);
}
return x;
}
else
{
assert(false);
}
}
}
string readString(int l, int r, char endd)
{
string ret = "";
int cnt = 0;
while(true)
{
char g = getchar();
assert(g != -1);
if(g == endd)
break;
cnt++;
ret += g;
}
assert(l <= cnt && cnt <= r);
return ret;
}
long long readIntSp(long long l, long long r) { return readInt(l, r, ' '); }
long long readIntLn(long long l, long long r) { return readInt(l, r, '\n'); }
string readStringLn(int l, int r) { return readString(l, r, '\n'); }
string readStringSp(int l, int r) { return readString(l, r, ' '); }
void readEOF() { assert(getchar() == EOF); }
vector<int> readVectorInt(int n, long long l, long long r)
{
vector<int> a(n);
for(int i = 0; i < n - 1; i++)
a[i] = readIntSp(l, r);
a[n - 1] = readIntLn(l, r);
return a;
}
// -------------------- Input Checker End --------------------
template<typename T,typename U>
struct suffix_array{
T s;
vector<int>p,c;
vector<int>lcp,len;
vector<vector<int>> st;
vector<int> LOG;
int n;
suffix_array(T str){
s=str;
n=s.size();p.resize(n);
c.resize(n);lcp.resize(n);
len.resize(n);
}
void count_sort(vector<int>&p,vector<int>&c){
int n=p.size();
vector<int>cnt(n);
for(auto x:c)cnt[x]++;
vector<int>p_new(n),pos(n);pos[0]=0;
for(int i=1;i<n;i++)pos[i]=pos[i-1]+cnt[i-1];
for(auto x:p){
int i=c[x];
p_new[pos[i]]=x;pos[i]++;
}
p=p_new;
}
void build(){
vector<pair<int,int>>a(n);
for(int i=0;i<n;i++)a[i]={s[i],i};
sort(all(a));
for(int i=0;i<n;i++)p[i]=a[i].y;
c[p[0]]=0;
for(int i=1;i<n;i++)c[p[i]]=(a[i].x==a[i-1].x)?c[p[i-1]]:c[p[i-1]]+1;
int k=0;
while((1<<k)<n){
for(int i=0;i<n;i++)p[i]=(p[i]-(1<<k)+n)%n;
count_sort(p,c);
vector<int>c_new(n);
c_new[p[0]]=0;
for(int i=1;i<n;i++){
pii prev={c[p[i-1]],c[(p[i-1]+(1<<k))%n]};
pii now={c[p[i]],c[(p[i]+(1<<k))%n]};
if(now==prev){
c_new[p[i]]=c_new[p[i-1]];
}
else{
c_new[p[i]]=c_new[p[i-1]]+1;
}
}
c=c_new;
k++;
}
for(int i=0;i<n;i++){
len[i]=n-p[i];
}
k=0;
for(int i=0;i<n-1;i++){
int pi=c[i];int j=p[pi-1];
while(s[i+k]==s[j+k])k++;
lcp[pi]=k;k=max(0LL,k-1);
}
}
void lcp_construct(){
st = vector<vector<int>>(20,vector<int>(n + 1));
LOG.resize(n + 1);
for(int i = 1; i < n; i++){
st[0][i] = lcp[i];
}
for(int i = 2; i < n; i++){
LOG[i] = 1 + LOG[i/2];
}
for(int x = 1; x < 20; x++){
for(int i = 1; i + (1 << (x - 1)) < n; i++){
st[x][i] = min(st[x - 1][i],st[x - 1][i + (1 << (x - 1))]);
}
}
}
int get_lcp(int i,int j){
int l = min(c[i],c[j]) + 1;
int r = max(c[i],c[j]);
int k = LOG[r - l + 1];
int ans = min(st[k][l],st[k][r - (1 << k) + 1]);
return ans;
}
bool compare(int l1, int r1,int l2, int r2){
if(l1 == l2)return r1 < r2;
auto res = get_lcp(l1,l2);
int len1 = r1 - l1 + 1;
int len2 = r2 - l2 + 1;
if(res >= len1 or res >= len2){
return len1 < len2;
}
return s[l1 + res] < s[l2 + res];
}
};
namespace PTree{
const int MAXN = 2e5 + 5;
struct node {
int next[26];
int len;
int sufflink;
int num;
};
int len;
node tree[MAXN];
int num; // node 1 - root with len -1, node 2 - root with len 0
int suff; // max suffix palindrome
bool addLetter(int pos,string &s,vector<pii> &segs) {
int cur = suff, curlen = 0;
int let = s[pos] - 'a';
while (true) {
curlen = tree[cur].len;
if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos])
break;
cur = tree[cur].sufflink;
}
if (tree[cur].next[let]) {
suff = tree[cur].next[let];
return false;
}
num++;
suff = num;
tree[num].len = tree[cur].len + 2;
tree[cur].next[let] = num;
segs.push_back({pos + 1 - tree[num].len,pos});
if (tree[num].len == 1) {
tree[num].sufflink = 2;
tree[num].num = 1;
return true;
}
while (true) {
cur = tree[cur].sufflink;
curlen = tree[cur].len;
if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) {
tree[num].sufflink = tree[cur].next[let];
break;
}
}
tree[num].num = 1 + tree[tree[num].sufflink].num;
return true;
}
void initTree() {
num = 2; suff = 2;
tree[1].len = -1; tree[1].sufflink = 1;
tree[2].len = 0; tree[2].sufflink = 1;
}
}
int solve(){
int n; cin >> n;
string s; cin >> s;
for(auto i:s){
assert(i >= 'a' and i <= 'z');
}
PTree::initTree();
vector<pii>segs;
for(int i = 0; i < n; i++){
PTree::addLetter(i,s,segs);
}
s += "$";
suffix_array<string,int> sa(s);
sa.build();
sa.lcp_construct();
sort(all(segs),[&](auto &a,auto &b){
return sa.compare(a.x,a.y,b.x,b.y);
});
vector<int> pref;
pref.push_back(segs[0].y - segs[0].x + 1);
for(int i = 1; i < segs.size(); i++){
pref.push_back(pref[i - 1] + segs[i].y - segs[i].x + 1);
}
int q; cin >> q;
auto get = [&](int i){
auto itr = lower_bound(all(pref),i) - pref.begin();
int reqd = i - 1;
if(itr > 0)reqd -= pref[itr - 1];
int l = segs[itr].x;
return s[l + reqd];
};
string t;
int sum = 0;
while(q--){
int l,r; cin >> l >> r;
assert(r >= l);
// int l = readIntSp(1,1e10);
// int r = readIntLn(l,1e10);
sum += r - l + 1;
assert(sum <= 5e5);
if(r > pref.back()){
cout << -1 << endl;
continue;
}
for(int i = l; i <= r; i++){
cout << get(i);
}cout << endl;
}
return 0;
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//freopen("input.txt", "r", stdin);
//freopen("output_3.txt", "w", stdout);
#ifdef SIEVE
sieve();
#endif
#ifdef NCR
init();
#endif
int t=1;//cin>>t;
while(t--){
solve();
}
return 0;
}
Tester (satyam_343)'s code (Hashing) (C++)
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define nline "\n"
#define f first
#define s second
#define pll pair<ll,ll>
#define all(x) x.begin(),x.end()
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vvvl vector<vector<vector<ll>>>
#ifndef ONLINE_JUDGE
#define debug(x) cerr<<#x<<" "; _print(x); cerr<<nline;
#else
#define debug(x);
#endif
void _print(ll x){cerr<<x;}
void _print(char x){cerr<<x;}
void _print(string x){cerr<<x;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T,class V> void _print(pair<T,V> p) {cerr<<"{"; _print(p.first);cerr<<","; _print(p.second);cerr<<"}";}
template<class T>void _print(vector<T> v) {cerr<<" [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T>void _print(set<T> v) {cerr<<" [ "; for (T i:v){_print(i); cerr<<" ";}cerr<<"]";}
template<class T>void _print(multiset<T> v) {cerr<< " [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T,class V>void _print(map<T, V> v) {cerr<<" [ "; for(auto i:v) {_print(i);cerr<<" ";} cerr<<"]";}
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<pair<ll,ll>, null_type, less<pair<ll,ll>>, rb_tree_tag, tree_order_statistics_node_update> ordered_pset;
//--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
const ll MOD=998244353;
const ll MOD1=1e9+7;
const ll MAX=300300;
ll binpow(ll a,ll b,ll MOD){
ll ans=1;
a%=MOD;
while(b){
if(b&1)
ans=(ans*a)%MOD;
b/=2;
a=(a*a)%MOD;
}
return ans;
}
ll inverse(ll a,ll MOD){
return binpow(a,MOD-2,MOD);
}
vector<ll> power(MAX,1),inv_power(MAX,1);
vector<ll> hashv(MAX,0),revhashv(MAX,0);
vector<ll> power1(MAX,1),inv_power1(MAX,1);
vector<ll> hashv1(MAX,0),revhashv1(MAX,0);
ll n;
ll gt_hash(ll l,ll r){
if(l>r){
return -1;
}
ll now=hashv[r]-hashv[l-1]+MOD;
now=(now*inv_power[l-1])%MOD;
ll now1=hashv1[r]-hashv1[l-1]+MOD1;
now1=(now1*inv_power1[l-1])%MOD1;
return now*now1;
}
ll gt_revhash(ll l,ll r){
ll now=(revhashv[l]-revhashv[r+1]+MOD);
now=(now*inv_power[n-r])%MOD;
ll now1=(revhashv1[l]-revhashv1[r+1]+MOD1);
now1=(now1*inv_power1[n-r])%MOD1;
return now*now1;
}
unordered_map<ll,ll> found;
const ll base=31;
string s;
ll comp(ll la,ll ra,ll lb,ll rb){
ll lena=ra-la+1,lenb=rb-lb+1;
ll l=0,r=min(lena,lenb),till=0;
while(l<=r){
ll mid=(l+r)/2;
if(gt_hash(la,la+mid-1)==gt_hash(lb,lb+mid-1)){
till=mid;
l=mid+1;
}
else{
r=mid-1;
}
}
if(till==min(lena,lenb)){
return lena==till;
}
if(s[la+till]<s[lb+till]){
return 1;
}
return 0;
}
const ll base1=29;
void solve(){
cin>>n;
cin>>s;
s=" "+s;
for(ll i=1;i<=n;i++){
power[i]=(power[i-1]*base)%MOD;
inv_power[i]=inverse(power[i],MOD);
power1[i]=(power1[i-1]*base1)%MOD1;
inv_power1[i]=inverse(power1[i],MOD1);
}
vector<pair<ll,ll>> segments;
for(ll i=1;i<=n;i++){
hashv[i]=(hashv[i-1]+(s[i]-'a'+1)*power[i])%MOD;
hashv1[i]=(hashv1[i-1]+(s[i]-'a'+1)*power1[i])%MOD1;
}
for(ll i=n;i>=1;i--){
revhashv[i]=(revhashv[i+1]+(s[i]-'a'+1)*power[n-i+1])%MOD;
revhashv1[i]=(revhashv1[i+1]+(s[i]-'a'+1)*power1[n-i+1])%MOD1;
}
for(ll i=1;i<=n;i++){
ll l=1,r=min(i,n+1-i),till=1;
while(l<=r){
ll mid=(l+r)/2;
if(gt_hash(i-mid+1,i+mid-1)==gt_revhash(i-mid+1,i+mid-1)){
till=mid;
l=mid+1;
}
else{
r=mid-1;
}
}
l=i-till+1,r=i+till-1;
while(l<=r and found.find(gt_hash(l,r))==found.end()){
found[gt_hash(l,r)]=1;
segments.push_back({l,r});
l++,r--;
}
l=0,r=min(i-1,n-i-1),till=-5;
while(l<=r){
ll mid=(l+r)/2;
if(gt_hash(i-mid,i+mid+1)==gt_revhash(i-mid,i+mid+1)){
till=mid;
l=mid+1;
}
else{
r=mid-1;
}
}
l=i-till,r=i+till+1;
while(l<=r and found.find(gt_hash(l,r))==found.end()){
found[gt_hash(l,r)]=1;
segments.push_back({l,r});
l++,r--;
}
}
sort(segments.begin(),segments.end(),[&](auto &l, auto &r){
return comp(l.f,l.s,r.f,r.s);
});
vector<ll> track;
ll prv=0;
for(auto it:segments){
track.push_back(prv+it.s-it.f+1);
prv=track.back();
}
ll m; cin>>m;
while(m--){
ll l,r; cin>>l>>r;
if(l>r){
cout<<"-1\n";
return;
}
if(r>track.back()){
cout<<"-1\n";
}
else{
while(l<=r){
ll pos=lower_bound(all(track),l)-track.begin();
auto it=segments[pos];
ll cur=track[pos]-(it.s-it.f+1);
ll need=l-cur;
cout<<s[it.f+need-1];
l++;
}
cout<<nline;
}
}
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("error.txt", "w", stderr);
#endif
ll test_cases=1;
//cin>>test_cases;
while(test_cases--){
solve();
}
cout<<fixed<<setprecision(10);
cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n";
}