@[zing_Sing](/user/627307) 你复制节点那里为什么要加到52，加到26就可以了吧
by UncleSam_Died @ 2023-07-17 20:11:05
@[UncleSam_Died](/user/378996) 可是不是大小写好像都有吗，样例中没体现出来
by zing_Sing @ 2023-07-17 20:12:36
附上蒟蒻的蒟蒻，模板（很水，大佬随便看看吧）
```cpp
#include<bits/stdc++.h>
using namespace std;
#define maxn 1000010
struct SuAM{
int link,len;//len记录长度，link记录连向哪个点
int ch[26];//记录每个字符出现的次数？
}SAM[maxn<<1];
int siz,last;
vector<int> SuffTree[maxn<<1];
inline void insert(const int c){//添加字符
int cur=++siz,p=last;//获取当前节点，获取上一个节点
SAM[cur].len=SAM[p].len+1;//当前节点的长度等于它的前缀（即上一个点）的长度加1
while(p!=-1&&!SAM[p].ch[c]){//如果父亲节点的字符集为空且父亲节点不为0（没有找到第一个点）
SAM[p].ch[c]=cur;//更新父亲节点每个字符出现的次数？
p=SAM[p].link;//通过link更新父亲节点，向上找
}
if(p==-1)//如果当前节点的上一个节点是0号节点（当前插入第一个）
SAM[cur].link=0;//把当前节点连向0号节点，把0号节点作为当前节点的父亲节点
else{
int q=SAM[p].ch[c];//用q来暂存p的出边
if(SAM[q].len==SAM[p].len+1)//如果当前节点的刚好为上一个节点+1
SAM[cur].link=q;//直接把这个节点连向上一个节点
else{
int copy=++siz;//新建一个点，把有关p的所有信息全部复制到新建节点中
SAM[copy].len=SAM[p].len+1;//新建节点的编号是p+1
SAM[copy].link=SAM[q].link;//新建节点的父节点更新为q的父节点
for(int i=0;i<26;i++)//遍历ch数组
SAM[copy].ch[i]=SAM[q].ch[i];//尝试连边
while(p!=-1&&SAM[p].ch[c]==q){
SAM[p].ch[c]=copy;
p=SAM[p].link;
}
SAM[q].link=SAM[cur].link=copy;//更新父亲节点
}
}
last=cur;//更新last，把当前节点作为下一个节点的上一个节点
}
char str[1000010];
int main(){
scanf("%s",&str);//以字符串的形式输入str
SAM[0].link=-1;//初始化link，把第一号点连向-1
int len=strlen(str);//获取长度
for(int i=0;i<len;i++) insert(str[i]-'a');//依次插入每一个字符
return 0;
}
```
by UncleSam_Died @ 2023-07-17 20:12:40
@[zing_Sing](/user/627307) 题中没说……你也可以认为128个都有……
by UncleSam_Died @ 2023-07-17 20:14:06
因为蒟蒻太弱了，读不懂洋文，理解有误勿喷
by UncleSam_Died @ 2023-07-17 20:14:31
@[UncleSam_Died](/user/378996) 可是我只写了大小写的情况也过了呀，代码如下：
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll t,n;
struct tree
{
ll son[52],f,len;
#define f(x) tr[x].f
#define l(x) tr[x].len
}tr[100005];
ll cnt=1,ls=1,ans[100005];
void add(ll x)
{
ll p=ls,np=ls=++cnt;
l(np)=l(p)+1;
for(;p&&!tr[p].son[x];p=f(p))tr[p].son[x]=np;
if(!p)f(np)=1;
else
{
ll q=tr[p].son[x];
if(l(q)==l(p)+1)f(np)=q;
else
{
ll nq=++cnt;
tr[nq]=tr[q];
l(nq)=l(p)+1;
f(q)=f(np)=nq;
for(;p&&tr[p].son[x]==q;p=f(p))tr[p].son[x]=nq;
}
}
}
string a;
void dfs(ll id)
{
if(ans[id])return;
ans[id]=1;
for(ll i=0;i<=51;++i)
if(tr[id].son[i])
dfs(tr[id].son[i]),ans[id]+=ans[tr[id].son[i]];
}
ll wz(ll id)
{
if('a'<=id&&id<='z')return id-'a';
return id-'A'+26;
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>t;
while(t--)
{
for(ll i=1;i<=1+2*n;++i)
ans[i]=0,memset(tr[i].son,0,sizeof(tr[i].son)),f(i)=l(i)=0;
cnt=ls=1;
cin>>a;
n=a.size();
for(ll i=0;i<n;++i)add(wz(a[i]));
dfs(1);
cout<<ans[1]-1<<'\n';
}
}
```
by NATO @ 2023-07-17 20:16:12
@[NATO](/user/443649) 好吧，谢谢大佬指点，蒟蒻刚学SAM3ts
by UncleSam_Died @ 2023-07-17 20:17:04
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e4+5;
int turn(int c){
if(c>='a'&&c<='z')return c-'a';
return c-'A'+26;
}
struct noi{
int ch[60],fa,len;
}sam[N];
int tot,las;
void addp(int c){
int p=las,np=las=++tot;
sam[np].len=sam[p].len+1;
for(;p&&!sam[p].ch[c];p=sam[p].fa)sam[p].ch[c]=np;
if(!p)sam[np].fa=1;
else{
int q=sam[p].ch[c];
if(sam[q].len==sam[p].len+1)sam[np].fa=q;
else{
int nq=++tot;
sam[nq]=sam[q];
sam[nq].len=sam[p].len+1;
sam[q].fa=sam[np].fa=nq;
for(;p&&sam[p].ch[c]==q;p=sam[p].fa)sam[p].ch[c]=nq;
}
}
}
int dp[N];
void dfs(int now){
if(dp[now])return;
dp[now]=1;
for(int i=0;i<=51;i++)
if(sam[now].ch[i])
dfs(sam[now].ch[i]),dp[now]+=dp[sam[now].ch[i]];
}
string s;
signed main(){
int t;
cin>>t;
int n=0;
while(t--){
for(int i=1;i<=2*n+1;i++){
memset(sam[i].ch,0,sizeof(sam[i].ch));
sam[i].len=sam[i].len=dp[i]=0;
}
tot=las=1;
cin>>s;
n=s.size();
for(int i=0;i<n;i++)
addp(turn(s[i]));
dfs(1);
cout<<dp[1]-1<<"\n";
}
return 0;
}
//目前位居亚军，加油！
```
@[zing_Sing](/user/627307) 改完了，是 $turn$函数的问题
by NATO @ 2023-07-17 20:38:12
@[UncleSam_Died](/user/378996) 谢谢dalao，真的有其他字符,把```turn```函数改了就对了%%%
by zing_Sing @ 2023-07-17 20:39:16
@[NATO](/user/443649) 谢谢dalao%%%
by zing_Sing @ 2023-07-17 20:40:02