牛客网 桂林电子科技大学第三届ACM程序设计竞赛 A.串串-后...
链接：https://ac.nowcoder.com/acm/contest/558/A来源：牛客网
A.串串
小猫在研究字符串。
小猫在研究字串。
给定一个长度为N的字符串S，问所有它的子串Sl…r(1≤l≤r≤N)，去重后有多少种。
输入描述:
一行一个字符串S。
输出描述:
一行一个整数，表示答案。
示例1
输入
复制
ababa
输出
复制9
备注: 1≤N≤10，字符都是小写字母后缀自动机模板题，因为数据太大，极限可能为1e10,要开long long
不会后缀自动机，贴个板子。
代码:
1 //A
2 #include<bits/stdc++.h>
3 using namespace std;
4 typedef long long ll;
5 const ll maxn =1e5+100;
6 char s;
7 ll len;
8 ll T;
9
10 struct SAM{
11 ll last,cnt,nxt,fa,l;
12 ll ans;
13 void init(){
14 last = cnt=1;
15 memset(nxt,0,sizeof nxt);
16 fa=0;ans=0;l=0;
17 }
18 ll inline newnode(){
19 ++cnt;
20 memset(nxt,0,sizeof nxt);
21 fa=l=0;
22 return cnt;
23 }
24 void add(ll c){
25 ll p = last;
26 ll np = newnode();
27 last = np;
28 l = l+1;
29 while (p&&!nxt){
30 nxt=np;
31 p = fa;
32 }
33 if (!p){
34 fa=1;
35 }else{
36 ll q = nxt;
37 if (l==l+1){
38 fa = q;
39 }else{
40 ll nq = newnode();
41 memcpy(nxt,nxt,sizeof nxt);
42 fa = fa;
43 l = l+1;
44 fa=fa=nq;
45 while (nxt==q){
46 nxt=nq;
47 p=fa;
48 }
49 }
50 }
51 // cout<<fa<<endl;
52 ans+=l-l];
53 }
54 void query(){
55 ll l,r;
56 l=1,r=len;
57 init();
58 for (ll i=l;i<=r;i++){
59 // cout<<s<<" ";
60 add(s-'a');
61 }
62 printf("%lld\n",ans);
63 }
64 }sam;
65
66 int main(){
67 scanf("%s",s+1);
68 len=strlen(s+1);
69 // cout<<len<<endl;
70 sam.query();
71 return 0;
72 }
文档来源：51CTO技术博客https://blog.51cto.com/u_15310764/3168003
页:
[1]