Distinct Substrings of a Moving Window
National Olympiad — National round (2020 season)
Submission name: substrings.cpp
Problem summary
Starting from a lowercase string, repeatedly append one letter at the end or remove the first letter. Report the number of distinct nonempty substrings initially and after every operation, including empty-string states.
Input
Initial string; Q; then operations 1 c (append) or 2 (remove first).
Output
Q+1 counts on one line.
Constraints
1 ≤ initial length ≤ 100,000; 0 ≤ Q ≤ 100,000; removals are valid.
Worked example
An independently prepared example for this explanation.
Input
abaababa 6 2 1 b 1 b 2 2 2
Output
24 19 23 31 24 17 14
Solution analysis
- Concatenate the initial string and all appended letters into one master string. Every state is a window [L,R] in this string. Process operations backward: removing the first letter becomes insertion of a suffix start at L−1, and appending becomes shortening every retained suffix by moving R left.
- Build the master suffix array and an LCP range-minimum structure. Keep suffix starts in suffix-array order, discarding any suffix that is a prefix of another retained suffix after truncation at R. Such a suffix adds no new substrings and remains redundant when all suffixes shorten or new suffixes are added. The union of prefix sets has size sum(lengths) minus the sum of LCPs of adjacent retained suffixes.
- For a retained suffix starting at i, its longest LCP with any other retained suffix is the maximum of its two neighbor LCPs. It becomes redundant when R≤i+thatLCP−1. A priority queue of these thresholds, with version stamps for changed neighbors, finds every expired suffix. Each insertion/removal changes only adjacent contributions; shortening R subtracts the retained suffix count. Thus all states are maintained without rebuilding a suffix structure.
Why it works
A substring of a window is a prefix of one of its truncated suffixes. In the master suffix order, common-prefix sets form contiguous ranges, so subtracting adjacent capped LCPs counts their union exactly, even during temporary prefix redundancies. Removing a suffix contained in another prefix set preserves this union; later uniform truncation and insertions cannot invalidate that containment. Once redundancies are removed, every adjacent LCP is shorter than both suffixes, so decreasing R by one changes only the length sum, by the number of retained suffixes. Neighbor LCP maxima detect exactly the next redundant suffixes. Local insertion/removal formulas preserve the union count, and reverse operations therefore reconstruct every requested answer.
Watch out. Truncate LCPs when calculating temporary insertion/removal contributions. Expired suffixes may trigger other expirations. Discard stale heap entries using versions. Counts require 64-bit arithmetic.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<numeric>
#include<queue>
#include<set>
#include<string>
#include<tuple>
#include<vector>
// Algorithm: Concatenate the initial string and all appended letters into one master string.
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
string text;
cin>>text;
int q;
cin>>q;
vector<int>operation(q);
int left=0;
for(int i=0;i<q;i++){
cin>>operation[i];
if(operation[i]==1){
char letter;
cin>>letter;
text+=letter;
}
else{
left++;
}
}
int n=static_cast<int>(text.size());
int right=n-1;
vector<int>suffix(n),rank(n),nextRank(n);
iota(suffix.begin(),suffix.end(),0);
for(int i=0;i<n;i++){
rank[i]=text[i]-'a';
}
for(int width=1;width<n;width*=2){
auto key=[&](int i){
return pair<int,int>(rank[i],i+width<n?rank[i+width]:-1);
};
sort(suffix.begin(),suffix.end(),[&](int a,int b){
return key(a)<key(b);
});
nextRank[suffix[0]]=0;
for(int i=1;i<n;i++){
nextRank[suffix[i]]=nextRank[suffix[i-1]]+(key(suffix[i-1])!=key(suffix[i]));
}
rank.swap(nextRank);
if(rank[suffix.back()]==n-1){
break;
}
}
for(int i=0;i<n;i++){
rank[suffix[i]]=i;
}
vector<int>lcp(n);
int common=0;
for(int i=0;i<n;i++){
int position=rank[i];
if(position==0){
common=0;
continue;
}
int j=suffix[position-1];
while(i+common<n&&j+common<n&&text[i+common]==text[j+common]){
common++;
}
lcp[position]=common;
common=max(0,common-1);
}
vector<int>logarithm(n+1);
for(int i=2;i<=n;i++){
logarithm[i]=logarithm[i/2]+1;
}
vector<vector<int>>minimum(logarithm[n]+1,vector<int>(n));
minimum[0]=lcp;
for(int level=1;level<=logarithm[n];level++){
for(int i=0;i+(1<<level)<=n;i++){
minimum[level][i]=min(minimum[level-1][i],minimum[level-1][i+(1<<(level-1))]);
}
}
auto fullLcp=[&](int a,int b){
if(a<0||b<0){
return 0;
}
if(a>b){
swap(a,b);
}
int length=b-a;
int level=logarithm[length];
return min(minimum[level][a+1],minimum[level][b-(1<<level)+1]);
};
auto cappedLcp=[&](int a,int b){
if(a<0||b<0){
return 0;
}
return min({fullLcp(a,b),right-suffix[a]+1,right-suffix[b]+1});
};
set<int>active;
vector<int>version(n);
priority_queue<tuple<int,int,int>>expiry;
long long answer=0;
auto neighbors=[&](set<int>::iterator it){
int before=it==active.begin()?-1:*prev(it);
int after=next(it)==active.end()?-1:*next(it);
return pair<int,int>(before,after);
};
auto refresh=[&](int position){
if(position<0){
return;
}
auto it=active.find(position);
if(it==active.end()){
return;
}
auto[before,after]=neighbors(it);
int shared=max(fullLcp(before,position),fullLcp(position,after));
expiry.emplace(suffix[position]+shared-1,position,++version[position]);
};
auto erase=[&](int position){
auto it=active.find(position);
auto[before,after]=neighbors(it);
answer-=right-suffix[position]+1;
answer+=cappedLcp(before,position)+cappedLcp(position,after)-cappedLcp(before,after);
active.erase(it);
version[position]++;
refresh(before);
refresh(after);
};
auto prune=[&](){
while(!expiry.empty()){
auto[threshold,position,stamp]=expiry.top();
if(stamp!=version[position]){
expiry.pop();
continue;
}
if(threshold<right){
break;
}
expiry.pop();
erase(position);
}
};
auto insert=[&](int start){
int position=rank[start];
auto it=active.insert(position).first;
auto[before,after]=neighbors(it);
answer+=right-start+1;
answer+=cappedLcp(before,after)-cappedLcp(before,position)-cappedLcp(position,after);
refresh(before);
refresh(position);
refresh(after);
prune();
};
for(int start=right;start>=left;start--){
insert(start);
}
vector<long long>answers(q+1);
answers[q]=answer;
for(int i=q-1;i>=0;i--){
if(operation[i]==1){
answer-=static_cast<long long>(active.size());
right--;
prune();
}
else{
insert(--left);
}
answers[i]=answer;
}
for(int i=0;i<=q;i++){
cout<<(i?" ":"")<<answers[i];
}
cout<<'\n';
}