Preface

This is not a profound academic research, this is just my own experience.

Hope it can help you.

Background

Not long ago I was confused while solving a problem "CF547E Mike and Friends", because of its memory limit.

I used generalized SAM and merge segment tree to solve it, but i got MLE for too many times TAT.

Pre knowledge

Segment tree merging

Segment tree merging can merge two dynamic open point weight segment trees in $$$O(n\log n)$$$ time.

SAM (Suffix Automaton)

SAM is a FSA (Finite State Automaton) that can maintain all suffixes of a string in $$$O(n)$$$ time and $$$O(n|\Sigma|)$$$ space, and support searching substrings.

Generalized SAM is SAM which maintains many strings. At first we set the root, and insert like common SAM. Additionally,pay attention to determine whether the current node already exists.

Create a suffix automaton for the reverse string,you can get the Suffix Tree.

So we use segment tree merging to modify the $$$endpos$$$,and the sum of it in a node means the appear times of substrings.

Main body

In CF547E, it gives you $$$n$$$ strings $$$s_n$$$, and you have $$$q$$$ querys to ask the appear times of $$$s_k$$$ in $$$s_l\ldots s_r$$$.

So I used Generalized SAM and Sgt merging. But as you know, it used $$$O(L\log L+ L |\Sigma|)$$$ space ($$$L=\sum_i |s_i|$$$), I finally got either MLE or RE.

Here is my code

#define in inline
#define pb push_back
const int N=2e5+5;
int n,m,lst=1,tot=1,fa[N<<1],ch[N<<1][26],len[N<<1],rt[N<<1],pos[N<<1],f[N<<1];
vector<int>e[N<<1];
in void ins(int c) // build Suffix Tree
{
    if(ch[lst][c]&&len[lst]+1==len[ch[lst][c]]) return lst=ch[lst][c],void(); // check 1
    int p=lst,np=lst=++tot;len[np]=len[p]+1;fa[np]=1;
    for(;!ch[p][c];p=fa[p]) ch[p][c]=np;
    if(p)
    {
        int q=ch[p][c];
        if(len[p]+1==len[q]) fa[np]=q;
        else
        {
            int nq=++tot;len[nq]=len[p]+1;if(len[p]+1==len[np]) lst=nq; // check 2
            fa[nq]=fa[q];memcpy(ch[nq],ch[q],4*26);fa[np]=fa[q]=nq;
            for(;ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
        }
    }
}
#define mid ((l+r)>>1)
int nd,ls[N*80],rs[N*80],s[N*80];
void ins(int &p,int l,int r,int x) // segment tree maintain the sum of endpos
{
    if(!p)p=++nd;s[p]++;if(l==r) return;
    x<=mid?ins(ls[p],l,mid,x):ins(rs[p],mid+1,r,x);
}
int ask(int p,int l,int r,int L,int R)
{
    if(!p||R<l||r<L) return 0;if(L<=l&&r<=R) return s[p];
    return ask(ls[p],l,mid,L,R)+ask(rs[p],mid+1,r,L,R);
}
int merge(int x,int y)
{
    if(!x||!y) return x+y;int p=++nd;s[p]=s[x]+s[y];
    ls[p]=merge(ls[x],ls[y]);rs[p]=merge(rs[x],rs[y]);return p;
}
void dfs(int u)
{
    for(int v:e[u]) f[v]=(len[u]==len[v]?f[u]:v),dfs(v),rt[u]=merge(rt[u],rt[v]);
}

Attention to this sgt merging

int merge(int x,int y)
{
    if(!x||!y) return x+y;int p=++nd;s[p]=s[x]+s[y];
    ls[p]=merge(ls[x],ls[y]);rs[p]=merge(rs[x],rs[y]);return p;
}

Of course it wastes lots of space, but you cannot use int &x.

Because after the original node is covered, it may still be called when asked, which will lead to wrong answer.

So a simple and feasible approach is to take the query offline, so that the node can be directly covered.

And another way is using AC Automaton and Persistent Segment tree, it only cost linear space.

But finally I didn't use the skills described above and got AC after hours of trying XD. OHHHHHHHHHHH

Other problems

Here is a similar Problem for you: CF666E (Nice Number)

The end

You can send comments if you have some questions or advice, and I'll be happy to watch and reply.