//Place your snippets for cpp here. Each snippet is defined under a snippet name and has a prefix, body and 
// description. The prefix is what is used to trigger the snippet and the body will be expanded and inserted. Possible variables are:
// $1, $2 for tab stops, $0 for the final cursor position, and ${1:label}, ${2:another} for placeholders. Placeholders with the 
// same ids are connected.
// prefix 的格式要求是 acm-[一级标题编号].[二级标题编号][该代码片段的英文简称]
// description 的格式要求是 "插入 [该代码片段的中文名]"

{
    "SAM转后缀树转后缀数组": {
        "prefix": "acm-6.6不同子串个数",
        "body": [
            "#include<algorithm>",
            "#include<cstring>",
            "#include<cstdio>",
            "#define LL long long",
            "#define Re register int",
            "using namespace std;",
            "const int N=1e5+5;",
            "int n;char s[N];LL ans;",
            "inline void in(Re &x){",
            "    int f=0;x=0;char c=getchar();",
            "    while(c<'0'||c>'9')f|=c=='-',c=getchar();",
            "    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();",
            "    x=f?-x:x;",
            "}",
            "struct Suffix_Array{",
            "\tint H[N],SA[N],rank[N],height[N];",
            "\tinline void get_height(){",
            "\t\tfor(Re i=1;i<=n;++i)rank[SA[i]]=i;",
            "\t\tfor(Re i=1,k=0;i<=n;++i){",
            "\t\t\tif(rank[i]==1)continue;",
            "\t\t\tif(k)--k;",
            "\t\t\tRe j=SA[rank[i]-1];",
            "\t\t\twhile(i+k<=n&&j+k<=n&&s[i+k]==s[j+k])++k;",
            "\t\t\theight[rank[i]]=H[i]=k;",
            "\t\t}",
            "\t}",
            "}SA;",
            "int pan[N<<1],pos[N<<1];",
            "struct Suffix_Tree{",
            "\tint t,tr[N<<1][26];",
            "\tinline void add(Re x,Re y,Re c){tr[x][c]=y;}",
            "\tinline void dfs(Re x){",
            "\t\tif(pan[x])SA.SA[++t]=pos[x];",
            "\t\tfor(Re i=0;i<26;++i)if(tr[x][i])dfs(tr[x][i]);",
            "\t}",
            "}ST;",
            "struct Suffix_Automaton{",
            "\tint O,last,link[N<<1],maxlen[N<<1],trans[N<<1][26];",
            "\tSuffix_Automaton(){last=O=1;}",
            "\tinline void insert(Re ch,Re id){",
            "\t\tRe z=++O,p=last;maxlen[z]=maxlen[p]+1,pan[z]=1,pos[z]=id;",
            "\t\twhile(p&&!trans[p][ch])trans[p][ch]=z,p=link[p];",
            "\t\tif(!p)link[z]=1;",
            "\t\telse{",
            "\t\t\tRe x=trans[p][ch];",
            "\t\t\tif(maxlen[p]+1==maxlen[x])link[z]=x;",
            "\t\t\telse{",
            "\t\t\t\tRe y=++O;maxlen[y]=maxlen[p]+1;",
            "\t\t\t\tfor(Re i=0;i<26;++i)trans[y][i]=trans[x][i];",
            "\t\t\t\twhile(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];",
            "\t\t\t\tpos[y]=pos[x],link[y]=link[x],link[x]=link[z]=y;",
            "\t\t\t}",
            "\t\t}",
            "\t\tlast=z;",
            "\t}",
            "\tinline void build(){",
            "\t\tfor(Re i=n;i>=1;--i)insert(s[i]-'a',i);",
            "\t\tfor(Re i=2;i<=O;++i)ST.add(link[i],i,s[pos[i]+maxlen[link[i]]]-'a');",
            "\t}",
            "}SAM;",
            "int main(){",
            "//\tfreopen(\"123.txt\",\"r\",stdin);",
            "\tin(n),scanf(\"%s\",s+1),SAM.build(),ST.dfs(1),SA.get_height();",
            "\tfor(Re i=1;i<=n;++i)ans+=n-SA.SA[i]+1-SA.height[i];",
            "\tprintf(\"%lld\\n\",ans);",
            "}",
            ""
        ],
        "description": "插入 SAM转后缀树转后缀数组"
    }
}