Approach
The idea is to use the Suffix Tree, which is quite obvious as we have to deal with multiple queries.
But how?
First, we have to build the suffix array.
-
We will read all the queries and ignore the ‘-’ to get the complete string first, and then we can reverse it to form our Suffix Array. So now,
- Query ‘+’ will stand to add a Suffix longer than all the existing ones while query ‘-’ will stand for delete the last char in all the suffix that is present.
Then we will proceed on building the segment tree with the following rules:
- The order of suffixes will be the same as they have in the suffix array.
- No suffix will be a prefix of other suffixes.
- Now let’s say we have any suffix, say ‘CUR’, and its previous suffix ‘PRE’, we will maintain and store Len(CUR) - LCP(CUR, PRE) for CUR(Let’s say this is ‘RL’). The same will be done for its next prefix. I.e., Len(CUR) - LCP(CUR,NEXT).(Let’s say this is ‘RR’) Here, LCP stands for the longest common prefix where whereas Len stands for the length of the string.
Now let’s talk about the remaining operations.
- When we add a new suffix, say ‘CUR’, we will check its previous suffix and the next suffix if either of them is the prefix of CUR. We will delete it.
- Now, whenever we have to delete a char from the suffix, we will see that all the RR and RL are reduced by 1. If any of them becomes 0, then we will delete it.
- Also answer at any instant is the sum of (Len(CUR) - LCP(CUR, PRE)) and ( Len(CUR) - LCP(CUR,NEXT)).i.e., ‘RL’ - ‘RR’ .This will be maintained in segment tree.
This might be a little overwhelming, but code will surely help you to grasp everything. Let us see the code.
Code
#include <cstdio>
#include <queue>
#include <cassert>
#include <cstring>
#include <iostream>
#include <algorithm>
using int64 = long long;
const int mod = 1e9 + 7;
const int N = 1e6 + 10,
inf = 1e9;
struct SuffixTree
{
struct node
{
// Following suffix link will lead to the vertex corresponding to the same substring, but without the first character.
node *go[26], *link, *fa;
int cnt, st, len;
node() {}
void clr()
{
st = cnt = 0;
len = inf;
link = fa = NULL;
memset(go, 0, sizeof(go));
}
}
pool[N *2], *rt, *ptr;
int s[N], n;
int64 dsc;
std::queue<node*> leaf;
struct position
{
node * u;
int cur;
int pos;
int rem;
position() {}
void go(int o)
{
u = u->go[o];
pos -= u->len;
cur += u->len;
}
bool can(int o)
{
return u->go[o] && pos >= u->go[o]->len;
}
}
last;
// For new node.
node* new_node(node *fa, int st, int len)
{
ptr->clr();
ptr->fa = fa;
ptr->st = st;
ptr->len = len;
if (fa) fa->cnt++;
return ptr++;
}
// Initializing.
void init()
{
n = 0, ptr = pool;
last.u = rt = new_node(NULL, 0, inf);
last.cur = last.pos = last.rem = 0;
dsc = 0;
}
void walk()
{
while (last.can(s[last.cur]))
{
last.go(s[last.cur]);
}
}
void follow_link()
{
if (last.u == rt)
{
if (last.pos) --last.pos, ++last.cur;
}
else last.u = last.u->link ? last.u->link : rt;
--last.rem;
}
void add(int c)
{
s[n++] = c;
++last.rem;
assert(last.pos >= 0);
for (node *p = rt; last.rem;)
{
if (!last.pos) last.cur = n - 1;
walk();
int o = s[last.cur];
node* &v = last.u->go[o];
int t = s[v == NULL ? 0 : v->st + last.pos];
if (v == NULL)
{
assert(last.pos == 0);
v = new_node(last.u, n - 1, inf);
leaf.push(v);
p->link = last.u;
p = rt;
}
else if (t == c)
{
p->link = last.u;
++last.pos;
return;
}
else
{
// split edge
node *u = new_node(last.u, v->st, last.pos);
last.u->cnt--;
u->go[c] = new_node(u, n - 1, inf);
leaf.push(u->go[c]);
u->go[t] = v;
++u->cnt;
v->fa = u;
v->st += last.pos;
v->len -= last.pos;
p->link = v = u;
p = u;
}
follow_link();
}
}
void del()
{
if (last.pos) walk();
auto x = leaf.front();
leaf.pop();
for (; x != last.u && !x->cnt; x = x->fa)
{
dsc -= std::min(n - x->st, x->len);
auto p = x->fa;
p->go[s[x->st]] = NULL;
p->cnt -= 1;
}
if (last.rem && x == last.u)
{
if (!last.pos && !x->cnt)
{
dsc -= std::min(n - x->st, x->len);
if (x->len != inf)
{
x->st = n - x->len;
x->len = inf;
}
dsc += std::min(n - x->st, x->len);
leaf.push(x);
}
else if (last.cur < n && !x->go[s[last.cur]])
{
auto u = new_node(x, n - last.pos, inf);
x->go[s[last.cur]] = u;
dsc += std::min(n - u->st, u->len);
leaf.push(u);
}
else
{
return;
}
follow_link();
}
}
void print(node *o)
{
printf("idx=%ld st=%d len=%d suf=%ld\n", o - pool, o->st, o->len, o->link ? o->link - pool : -1);
for (int i = 0; i < 26; ++i)
if (o->go[i])
{
assert(o->go[i]->fa == o);
printf("%ld -> %ld\n", o - pool, o->go[i] - pool);
print(o->go[i]);
}
}
void solve()
{
init();
int q;
scanf("%d", &q);
int64 ret = 0;
for (int i = 0; i < q; ++i)
{
char op;
scanf(" %c", &op);
if (op == '+')
{
char c;
scanf(" %c", &c);
add(c - 'a');
dsc += leaf.size();
}
else
{
del();
}
ret += dsc % mod;
}
printf("%lld\n", ret % mod);
}
}
suffix_tree;
int main()
{
suffix_tree.solve();
return 0;
}
You can also try this code with Online C++ Compiler
Input
4
+ a
+ b
-
+ a
Output
8
Time Complexity
O(Q * log (Q)), where ‘Q’ is the number of queries.
This is because we are using a segment tree, and we will make a total of Q queries, and for each query, it will cost us log (Q) time, which is the usual time taken by inserting and deleting of segment tree. Thus, the overall time complexity is O(Q * log(Q)).
Space Complexity
O((2 * Q) - 1), where ‘Q’ is the number of queries.
As we are using a suffix array, there will be a total of Q nodes.
Check out this problem - Longest Common Prefix
Key Takeaways
We saw how we solved the ‘Queuing problem’ using suffix trees in a very reduced time. It was hard to grasp, but we are proud that our ninja helped you in understanding it. Now, You must be thrilled about learning a new concept, but the road to become a competitive coder is still very long. So head over to our practice platform Coding Ninjas Studio to practice top problems on every topic, interview experiences, and many more. You can also consider our competitive programming course to give your career an edge over others. Till then, Happy Coding!
518+ registered 
