#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
#include <numeric>
#include <set>
using namespace std;
#define endl '\n'
struct SuffixArrayTree
{
SuffixArrayTree() : root(-1), up(1), sa(1)
{
root = new_node(-1, -1);
}
void push(int c)
{
int old_root = root;
root = new_node(c, root);
if (old_root != -1)
children[old_root].push_back(root);
queries.push_back(root);
}
void pop()
{
assert(root != -1);
root = up[0][root];
queries.push_back(root);
}
void record()
{
queries.clear();
queries.push_back(root);
}
int compare(int u, int v, vector<int> &up, vector<int> &sa, vector<int> &len)
{
if (sa[u] != sa[v])
return sa[u] < sa[v] ? +1 : -1;
if (up[u] == -1 || up[v] == -1)
{
if (len[u] == len[v])
return 0;
return len[u] < len[v] ? +1 : -1;
}
u = up[u], v = up[v];
if (sa[u] == sa[v])
return 0;
return sa[u] < sa[v] ? +1 : -1;
}
void build()
{
int n = sa[0].size();
// compute len of each string
for (int i = 0; i < n; ++i)
{
if (up[0][i] == -1)
len[i] = 0;
else
len[i] = len[up[0][i]] + 1;
}
// Build suffix array
for (int i = 0; i < 20; ++i)
{
vector<int> u(n), s(n); // up row + suffix array row
auto &ub = up.back();
auto &sb = sa.back();
for (int i = 0; i < n; ++i)
u[i] = ub[i] == -1 ? -1 : ub[ub[i]];
iota(s.begin(), s.end(), 0);
sort(s.begin(), s.end(), [&](int &u, int &v)
{ return compare(u, v, ub, sb, len) == +1; });
vector<int> row(n);
for (int i = 1; i < n; ++i)
{
int u = s[i - 1], v = s[i];
int c = compare(u, v, ub, sb, len);
assert(c >= 0);
row[v] = row[u] + c;
}
order = s;
up.push_back(u);
sa.push_back(row);
}
rank = vector<int>(n);
for (int i = 0; i < n; ++i)
rank[order[i]] = i;
// Build lcp
lcp = vector<int>(n - 1);
for (int i = 0; i + 1 < n; ++i)
lcp[i] = find_lcp_log(order[i], order[i + 1]);
// Build rmq table for lcp
rmq.push_back(lcp);
for (int i = 1; (1 << i) <= n - 1; ++i)
{
vector<int> r(n - 1);
for (int j = 0; j + (1 << i) <= n - 1; ++j)
r[j] = min(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]);
rmq.push_back(r);
}
log2 = vector<int>(n + 1);
for (int i = 2; i <= n; ++i)
log2[i] = 1 + log2[i / 2];
set<int> s;
dfs(0, s);
}
void print()
{
for (auto u : queries)
cout << answer[u] << '\n';
}
private:
int root;
vector<int> order, rank, lcp, log2, len, queries;
vector<long long> answer;
vector<vector<int>> up, rmq, sa, children;
int new_node(int value, int parent)
{
sa.back().push_back(value);
up.back().push_back(parent);
len.push_back(0);
answer.push_back(0);
children.push_back({});
return sa.back().size() - 1;
}
int find_lcp_log(int u, int v)
{
int answer = 0;
for (int l = sa.size() - 1; u != -1 && v != -1 && l >= 0; --l)
{
if ((1 << l) <= len[u] && sa[l][u] == sa[l][v])
{
answer += 1 << l;
u = up[l][u];
v = up[l][v];
}
}
return answer;
}
int find_lcp_from_rank(int pu, int pv)
{
// int pu = rank[u];
// int pv = rank[v];
if (pu > pv)
swap(pu, pv);
pv--;
int sz = pv - pu + 1;
int lg = log2[sz];
return min(rmq[lg][pu], rmq[lg][pv - (1 << lg) + 1]);
}
void dfs(int u, set<int> &s)
{
// Try insert
int r = rank[u];
auto it = s.lower_bound(r);
// [l2] ... [l1] ... [r] ... [r1] ... [r2]
int l2 = 0, l1 = 0, r1 = 0, r2 = 0, c = 0;
if (it != s.end())
{
if (it != s.begin())
{
int b = *--it;
int a = *++it;
c = find_lcp_from_rank(a, b);
}
r1 = find_lcp_from_rank(r, *it);
if (++it != s.end())
r2 = find_lcp_from_rank(r, *it);
--it;
}
if (it != s.begin())
{
l1 = find_lcp_from_rank(*--it, r);
if (it != s.begin())
l2 = find_lcp_from_rank(*--it, r);
}
int new_delta = max(l1, r1) - max({l2, r2, c});
answer[u] += new_delta;
s.insert(r);
for (auto v : children[u])
{
answer[v] = answer[u];
dfs(v, s);
}
s.erase(r);
}
};
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
string s, q;
cin >> s >> q;
SuffixArrayTree tree;
for (auto c : s)
tree.push(c - 'A');
tree.record();
for (auto c : q)
{
if (c == '-')
tree.pop();
else
tree.push(c - 'A');
}
tree.build();
tree.print();
}
I2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPGNhc3NlcnQ+CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPG51bWVyaWM+CiNpbmNsdWRlIDxzZXQ+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwojZGVmaW5lIGVuZGwgJ1xuJwoKc3RydWN0IFN1ZmZpeEFycmF5VHJlZQp7CgogICAgU3VmZml4QXJyYXlUcmVlKCkgOiByb290KC0xKSwgdXAoMSksIHNhKDEpCiAgICB7CiAgICAgICAgcm9vdCA9IG5ld19ub2RlKC0xLCAtMSk7CiAgICB9CgogICAgdm9pZCBwdXNoKGludCBjKQogICAgewogICAgICAgIGludCBvbGRfcm9vdCA9IHJvb3Q7CiAgICAgICAgcm9vdCA9IG5ld19ub2RlKGMsIHJvb3QpOwogICAgICAgIGlmIChvbGRfcm9vdCAhPSAtMSkKICAgICAgICAgICAgY2hpbGRyZW5bb2xkX3Jvb3RdLnB1c2hfYmFjayhyb290KTsKICAgICAgICBxdWVyaWVzLnB1c2hfYmFjayhyb290KTsKICAgIH0KCiAgICB2b2lkIHBvcCgpCiAgICB7CiAgICAgICAgYXNzZXJ0KHJvb3QgIT0gLTEpOwogICAgICAgIHJvb3QgPSB1cFswXVtyb290XTsKICAgICAgICBxdWVyaWVzLnB1c2hfYmFjayhyb290KTsKICAgIH0KCiAgICB2b2lkIHJlY29yZCgpCiAgICB7CiAgICAgICAgcXVlcmllcy5jbGVhcigpOwogICAgICAgIHF1ZXJpZXMucHVzaF9iYWNrKHJvb3QpOwogICAgfQoKICAgIGludCBjb21wYXJlKGludCB1LCBpbnQgdiwgdmVjdG9yPGludD4gJnVwLCB2ZWN0b3I8aW50PiAmc2EsIHZlY3RvcjxpbnQ+ICZsZW4pCiAgICB7CiAgICAgICAgaWYgKHNhW3VdICE9IHNhW3ZdKQogICAgICAgICAgICByZXR1cm4gc2FbdV0gPCBzYVt2XSA/ICsxIDogLTE7CiAgICAgICAgaWYgKHVwW3VdID09IC0xIHx8IHVwW3ZdID09IC0xKQogICAgICAgIHsKICAgICAgICAgICAgaWYgKGxlblt1XSA9PSBsZW5bdl0pCiAgICAgICAgICAgICAgICByZXR1cm4gMDsKICAgICAgICAgICAgcmV0dXJuIGxlblt1XSA8IGxlblt2XSA/ICsxIDogLTE7CiAgICAgICAgfQogICAgICAgIHUgPSB1cFt1XSwgdiA9IHVwW3ZdOwogICAgICAgIGlmIChzYVt1XSA9PSBzYVt2XSkKICAgICAgICAgICAgcmV0dXJuIDA7CiAgICAgICAgcmV0dXJuIHNhW3VdIDwgc2Fbdl0gPyArMSA6IC0xOwogICAgfQoKICAgIHZvaWQgYnVpbGQoKQogICAgewogICAgICAgIGludCBuID0gc2FbMF0uc2l6ZSgpOwoKICAgICAgICAvLyBjb21wdXRlIGxlbiBvZiBlYWNoIHN0cmluZwogICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbjsgKytpKQogICAgICAgIHsKICAgICAgICAgICAgaWYgKHVwWzBdW2ldID09IC0xKQogICAgICAgICAgICAgICAgbGVuW2ldID0gMDsKICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgbGVuW2ldID0gbGVuW3VwWzBdW2ldXSArIDE7CiAgICAgICAgfQoKICAgICAgICAvLyBCdWlsZCBzdWZmaXggYXJyYXkKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IDIwOyArK2kpCiAgICAgICAgewogICAgICAgICAgICB2ZWN0b3I8aW50PiB1KG4pLCBzKG4pOyAvLyB1cCByb3cgKyBzdWZmaXggYXJyYXkgcm93CgogICAgICAgICAgICBhdXRvICZ1YiA9IHVwLmJhY2soKTsKICAgICAgICAgICAgYXV0byAmc2IgPSBzYS5iYWNrKCk7CgogICAgICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IG47ICsraSkKICAgICAgICAgICAgICAgIHVbaV0gPSB1YltpXSA9PSAtMSA/IC0xIDogdWJbdWJbaV1dOwoKICAgICAgICAgICAgaW90YShzLmJlZ2luKCksIHMuZW5kKCksIDApOwogICAgICAgICAgICBzb3J0KHMuYmVnaW4oKSwgcy5lbmQoKSwgWyZdKGludCAmdSwgaW50ICZ2KQogICAgICAgICAgICAgICAgIHsgcmV0dXJuIGNvbXBhcmUodSwgdiwgdWIsIHNiLCBsZW4pID09ICsxOyB9KTsKCiAgICAgICAgICAgIHZlY3RvcjxpbnQ+IHJvdyhuKTsKICAgICAgICAgICAgZm9yIChpbnQgaSA9IDE7IGkgPCBuOyArK2kpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGludCB1ID0gc1tpIC0gMV0sIHYgPSBzW2ldOwogICAgICAgICAgICAgICAgaW50IGMgPSBjb21wYXJlKHUsIHYsIHViLCBzYiwgbGVuKTsKICAgICAgICAgICAgICAgIGFzc2VydChjID49IDApOwogICAgICAgICAgICAgICAgcm93W3ZdID0gcm93W3VdICsgYzsKICAgICAgICAgICAgfQoKICAgICAgICAgICAgb3JkZXIgPSBzOwogICAgICAgICAgICB1cC5wdXNoX2JhY2sodSk7CiAgICAgICAgICAgIHNhLnB1c2hfYmFjayhyb3cpOwogICAgICAgIH0KCiAgICAgICAgcmFuayA9IHZlY3RvcjxpbnQ+KG4pOwogICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbjsgKytpKQogICAgICAgICAgICByYW5rW29yZGVyW2ldXSA9IGk7CgogICAgICAgIC8vIEJ1aWxkIGxjcAogICAgICAgIGxjcCA9IHZlY3RvcjxpbnQ+KG4gLSAxKTsKICAgICAgICBmb3IgKGludCBpID0gMDsgaSArIDEgPCBuOyArK2kpCiAgICAgICAgICAgIGxjcFtpXSA9IGZpbmRfbGNwX2xvZyhvcmRlcltpXSwgb3JkZXJbaSArIDFdKTsKCiAgICAgICAgLy8gQnVpbGQgcm1xIHRhYmxlIGZvciBsY3AKICAgICAgICBybXEucHVzaF9iYWNrKGxjcCk7CiAgICAgICAgZm9yIChpbnQgaSA9IDE7ICgxIDw8IGkpIDw9IG4gLSAxOyArK2kpCiAgICAgICAgewogICAgICAgICAgICB2ZWN0b3I8aW50PiByKG4gLSAxKTsKICAgICAgICAgICAgZm9yIChpbnQgaiA9IDA7IGogKyAoMSA8PCBpKSA8PSBuIC0gMTsgKytqKQogICAgICAgICAgICAgICAgcltqXSA9IG1pbihybXFbaSAtIDFdW2pdLCBybXFbaSAtIDFdW2ogKyAoMSA8PCAoaSAtIDEpKV0pOwogICAgICAgICAgICBybXEucHVzaF9iYWNrKHIpOwogICAgICAgIH0KCiAgICAgICAgbG9nMiA9IHZlY3RvcjxpbnQ+KG4gKyAxKTsKICAgICAgICBmb3IgKGludCBpID0gMjsgaSA8PSBuOyArK2kpCiAgICAgICAgICAgIGxvZzJbaV0gPSAxICsgbG9nMltpIC8gMl07CgogICAgICAgIHNldDxpbnQ+IHM7CiAgICAgICAgZGZzKDAsIHMpOwogICAgfQoKICAgIHZvaWQgcHJpbnQoKQogICAgewogICAgICAgIGZvciAoYXV0byB1IDogcXVlcmllcykKICAgICAgICAgICAgY291dCA8PCBhbnN3ZXJbdV0gPDwgJ1xuJzsKICAgIH0KCnByaXZhdGU6CiAgICBpbnQgcm9vdDsKICAgIHZlY3RvcjxpbnQ+IG9yZGVyLCByYW5rLCBsY3AsIGxvZzIsIGxlbiwgcXVlcmllczsKICAgIHZlY3Rvcjxsb25nIGxvbmc+IGFuc3dlcjsKICAgIHZlY3Rvcjx2ZWN0b3I8aW50Pj4gdXAsIHJtcSwgc2EsIGNoaWxkcmVuOwoKICAgIGludCBuZXdfbm9kZShpbnQgdmFsdWUsIGludCBwYXJlbnQpCiAgICB7CiAgICAgICAgc2EuYmFjaygpLnB1c2hfYmFjayh2YWx1ZSk7CiAgICAgICAgdXAuYmFjaygpLnB1c2hfYmFjayhwYXJlbnQpOwogICAgICAgIGxlbi5wdXNoX2JhY2soMCk7CiAgICAgICAgYW5zd2VyLnB1c2hfYmFjaygwKTsKICAgICAgICBjaGlsZHJlbi5wdXNoX2JhY2soe30pOwogICAgICAgIHJldHVybiBzYS5iYWNrKCkuc2l6ZSgpIC0gMTsKICAgIH0KCiAgICBpbnQgZmluZF9sY3BfbG9nKGludCB1LCBpbnQgdikKICAgIHsKICAgICAgICBpbnQgYW5zd2VyID0gMDsKCiAgICAgICAgZm9yIChpbnQgbCA9IHNhLnNpemUoKSAtIDE7IHUgIT0gLTEgJiYgdiAhPSAtMSAmJiBsID49IDA7IC0tbCkKICAgICAgICB7CiAgICAgICAgICAgIGlmICgoMSA8PCBsKSA8PSBsZW5bdV0gJiYgc2FbbF1bdV0gPT0gc2FbbF1bdl0pCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGFuc3dlciArPSAxIDw8IGw7CiAgICAgICAgICAgICAgICB1ID0gdXBbbF1bdV07CiAgICAgICAgICAgICAgICB2ID0gdXBbbF1bdl07CiAgICAgICAgICAgIH0KICAgICAgICB9CgogICAgICAgIHJldHVybiBhbnN3ZXI7CiAgICB9CgogICAgaW50IGZpbmRfbGNwX2Zyb21fcmFuayhpbnQgcHUsIGludCBwdikKICAgIHsKICAgICAgICAvLyBpbnQgcHUgPSByYW5rW3VdOwogICAgICAgIC8vIGludCBwdiA9IHJhbmtbdl07CiAgICAgICAgaWYgKHB1ID4gcHYpCiAgICAgICAgICAgIHN3YXAocHUsIHB2KTsKICAgICAgICBwdi0tOwogICAgICAgIGludCBzeiA9IHB2IC0gcHUgKyAxOwogICAgICAgIGludCBsZyA9IGxvZzJbc3pdOwogICAgICAgIHJldHVybiBtaW4ocm1xW2xnXVtwdV0sIHJtcVtsZ11bcHYgLSAoMSA8PCBsZykgKyAxXSk7CiAgICB9CgogICAgdm9pZCBkZnMoaW50IHUsIHNldDxpbnQ+ICZzKQogICAgewogICAgICAgIC8vIFRyeSBpbnNlcnQKICAgICAgICBpbnQgciA9IHJhbmtbdV07CiAgICAgICAgYXV0byBpdCA9IHMubG93ZXJfYm91bmQocik7CgogICAgICAgIC8vIFtsMl0gLi4uIFtsMV0gLi4uIFtyXSAuLi4gW3IxXSAuLi4gW3IyXQogICAgICAgIGludCBsMiA9IDAsIGwxID0gMCwgcjEgPSAwLCByMiA9IDAsIGMgPSAwOwoKICAgICAgICBpZiAoaXQgIT0gcy5lbmQoKSkKICAgICAgICB7CiAgICAgICAgICAgIGlmIChpdCAhPSBzLmJlZ2luKCkpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGludCBiID0gKi0taXQ7CiAgICAgICAgICAgICAgICBpbnQgYSA9ICorK2l0OwogICAgICAgICAgICAgICAgYyA9IGZpbmRfbGNwX2Zyb21fcmFuayhhLCBiKTsKICAgICAgICAgICAgfQoKICAgICAgICAgICAgcjEgPSBmaW5kX2xjcF9mcm9tX3JhbmsociwgKml0KTsKICAgICAgICAgICAgaWYgKCsraXQgIT0gcy5lbmQoKSkKICAgICAgICAgICAgICAgIHIyID0gZmluZF9sY3BfZnJvbV9yYW5rKHIsICppdCk7CiAgICAgICAgICAgIC0taXQ7CiAgICAgICAgfQoKICAgICAgICBpZiAoaXQgIT0gcy5iZWdpbigpKQogICAgICAgIHsKICAgICAgICAgICAgbDEgPSBmaW5kX2xjcF9mcm9tX3JhbmsoKi0taXQsIHIpOwogICAgICAgICAgICBpZiAoaXQgIT0gcy5iZWdpbigpKQogICAgICAgICAgICAgICAgbDIgPSBmaW5kX2xjcF9mcm9tX3JhbmsoKi0taXQsIHIpOwogICAgICAgIH0KCiAgICAgICAgaW50IG5ld19kZWx0YSA9IG1heChsMSwgcjEpIC0gbWF4KHtsMiwgcjIsIGN9KTsKCiAgICAgICAgYW5zd2VyW3VdICs9IG5ld19kZWx0YTsKCiAgICAgICAgcy5pbnNlcnQocik7CgogICAgICAgIGZvciAoYXV0byB2IDogY2hpbGRyZW5bdV0pCiAgICAgICAgewogICAgICAgICAgICBhbnN3ZXJbdl0gPSBhbnN3ZXJbdV07CiAgICAgICAgICAgIGRmcyh2LCBzKTsKICAgICAgICB9CgogICAgICAgIHMuZXJhc2Uocik7CiAgICB9Cn07CgppbnQgbWFpbigpCnsKICAgIGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oMCk7CiAgICBjaW4udGllKDApOwoKICAgIHN0cmluZyBzLCBxOwogICAgY2luID4+IHMgPj4gcTsKCiAgICBTdWZmaXhBcnJheVRyZWUgdHJlZTsKCiAgICBmb3IgKGF1dG8gYyA6IHMpCiAgICAgICAgdHJlZS5wdXNoKGMgLSAnQScpOwoKICAgIHRyZWUucmVjb3JkKCk7CgogICAgZm9yIChhdXRvIGMgOiBxKQogICAgewogICAgICAgIGlmIChjID09ICctJykKICAgICAgICAgICAgdHJlZS5wb3AoKTsKICAgICAgICBlbHNlCiAgICAgICAgICAgIHRyZWUucHVzaChjIC0gJ0EnKTsKICAgIH0KCiAgICB0cmVlLmJ1aWxkKCk7CiAgICB0cmVlLnByaW50KCk7Cn0K