刚学ＯＩ萌新想请神仙们指点一下卡空间技巧

#include<bits/stdc++.h>

using namespace std;

int n,m;

struct SAM
{
    struct Node
    {
        int link;
        map<int,int>ptr;
        int len,endpos;

        Node():link(0),len(0),endpos(0){}

        Node(int link,int len):link(link),len(len),endpos(0){}
    }nd[600000];
    int cnt,last;

    SAM():cnt(1),last(1){}

    void extend(int x,int pos)
    {
        int now=++cnt;
        nd[now].len=nd[last].len+1;
        nd[now].endpos=pos;
        int p=last;
        while(p&&!nd[p].ptr[x])
        {
            nd[p].ptr[x]=now;
            p=nd[p].link;
        }
        if(!p)
        {
            nd[now].link=1;
        }
        else
        {
            int q=nd[p].ptr[x];
            if(nd[p].len+1==nd[q].len)
            {
                nd[now].link=q;
            }
            else
            {
                int clone=++cnt;
                nd[clone]=Node(nd[q].link,nd[p].len+1);
                nd[clone].ptr=nd[q].ptr;
                while(p&&nd[p].ptr[x]==q)
                {
                    nd[p].ptr[x]=clone;
                    p=nd[p].link;
                }
                nd[q].link=nd[now].link=clone;
            }
        }
        last=now;
    }

    int topo[600001];

    void gettop()
    {
        int *tax=new int[300001];
        for(int i=1;i<=n;i++)
        {
            tax[i]=0;
        }
        for(int i=1;i<=cnt;i++)
        {
            tax[nd[i].len]++;
        }
        for(int i=1;i<=n;i++)
        {
            tax[i]+=tax[i-1];
        }
        for(int i=1;i<=cnt;i++)
        {
            topo[tax[nd[i].len]--]=i;
        }
        delete[] tax;
    }
}A;

string s;

int maxx[600000];
int ans[300001];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>s;
    for(int i=1;i<=n;i++)
    {
        A.extend(s[i-1]-'a',i);
    }
    A.gettop();
    cin>>m;
    while(m--)
    {
        cin>>s;
        int len=s.size(),now=1;
        for(int i=0;i<len;i++)
        {
            now=A.nd[now].ptr[s[i]-'a'];
            if(!now) break;
        }
        if(now)
        {
            maxx[now]=max(maxx[now],len);
        }
    }
    for(int i=1;i<=A.cnt;i++)
    {
        int x=A.topo[i];
        maxx[x]=max(maxx[A.nd[x].link],maxx[x]);
        if(maxx[x]&&A.nd[x].endpos)
        {
            ans[A.nd[x].endpos-maxx[x]+1]++;
            ans[A.nd[x].endpos+1]--;
        }
    }
    for(int i=1;i<=n;i++)
    {
        ans[i]+=ans[i-1];
    }
    int res=0;
    for(int i=1;i<=n;i++)
    {
        res+=(ans[i]==0);
    }
    cout<<res<<'\n';
}