1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 100005
#define N 200005
#define LL long long
using namespace std;
struct SAM{
    int n,ch[N][26],sg[N],fr[N],len[N],tot;
    LL cnt[N][28];
    char S[M];
    void NewNode(int &p,int d,int pl,int f){
        p=++tot;
        len[p]=d,fr[p]=f;
        if(pl==-1)for(int i=0;i<26;i++)ch[p][i]=-1;
        else for(int i=0;i<26;i++)ch[p][i]=ch[pl][i];
    }
    void Addchar(int u,int &p,int c){
        NewNode(p,len[u]+1,-1,-1);
        int v=u;
        while(v!=-1&&ch[v][c]==-1){
            ch[v][c]=p;
            v=fr[v];
        }
        if(v==-1){
            fr[p]=0;
            return;
        }
        int x=ch[v][c],y;
        if(len[x]==len[v]+1){
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX