字符串(str.*)
题目描述
Diaoyeye 正在研究字符串。nyx向他问了一个问题：有一个字符串𝑆，其中不同子串的 个数。
Diaoyeye 显然直接秒掉。他现在想问一问 nyx ，有一个字符串 \(𝑆\)，从中选出两个子串 \(A\)，\(𝐵\)，求 \(𝐴+𝐵\) 可以构成的不同串的个数。Diaoyeye还想知道，这么多个串中字典序最大的那一个。nyx 把这个问题扔给了你。
输入描述
一个全由小写字母构成的字符串 \(𝑆\)。
输出描述
第一行一个非负整数，表示两个子串 \(A+𝐵\) 可以构成的不同串的个数。由于答案可能很 大，所以答案对 \(1004535809\) 取模。
第二行一个字符串，表示构成的串中字典序最大的。
输入输出样例
输入样例#1
ab
输出样例#1
11
bb
输入样例#2
abcaabccba
输出样例#2
1428
ccccba
说明/提示
对于字符串 \(A\) 和 \(B\)
两个子串均可为空，但不同时为空。
样例#1的解释
可以构成的串有：\(\tt{a}\)，\(\tt{b}\)，$ \tt{aa} \(，\) \tt{aab} \(，\) \tt{ab} \(，\) \tt{aba} \(，\) \tt{abab} \(，\)\tt{abb}\(，\)\tt{ba}\(，\)\tt{bab}\(，\)\tt{bb}$。共 \(11\) 种。
字典序最大的是 \(\tt{bb}\)。
数据范围
设 \(n=|S|\)。
- 对于 \(10\)% 的数据，\(n \leq 10\)。
- 对于 \(30\)% 的数据，\(n \leq 40\)。
- 另有 \(20\)% 的数据，字符串由 \(1\) 个 \(a\) 字符和 \(n-1\) 个 \(b\) 字符组成。
- 对于 \(100\)% 的数据，\(n \leq 2000\)。
解题报告
不得不说，我的字符串学成一坨。
这个问题的第二问比较简单，第一问比较难。
先讲第一问。
先考虑暴力的写法，我们穷举所有子串，然后考虑判重。显然第一个反应是直接上哈希，但是这回把我们的之后路给堵上。我们寻找使 \(A+B\) 不重的条件。
显然，设 \(B_i\) 为字符串 \(B\) 的第 \(i\) 个字符，\(B_{[l,r]}\) 为字符串 \(B\) 第 \(l\) 到第 \(r\) 个字符，当被计算的方案满足 \(A+B_1\) 不是 \(S\) 的子串（断句：不是 / \(S\) 的子串）时，这个方案肯定不重。至于为什么，假设\(A+B_1\) 是 \(S\) 的某一个子串，我们就可以把令一个新的 \(A'=A+B_1\) 和 \(B'=B_{2,n}\)，这个方案与之前的一样。
定义 \(head_c\) 为串 \(S\) 中以字母 \(c\) 开头的不同非空子串的个数，\(tail_c\) 为串 \(S\) 中加上字母 \(u\) 以后不为 \(S\) 的子串的不同非空字符串的个数。
显然有：\(ans=\sum_{c='a'}^{'z'} head_c \times (tail_c+1)\)。
怎么计算 \(head_c\) 和 \(tail_c\)？同时，怎么处理子串重复的问题？
由于 \(n \leq 2000\)，我们就残暴一点，直接把所有的子串插进一个 trie 树中实现去重，显然，我们实际上构造了一颗前缀树。那么 \(head_c\) 就是 trie 树中与根节点相连的子树大小，而对于 \(tail_c\) 则遍历一遍 trie 树，对于每一个节点 \(u\)，若字符 \(c\) 满足 \(trie[u].ch[c]==0\) 且 \(trie[0]!=0\) 的个数，则 \(tail_c++\)。
对于第二问，直接贪心就好了，答案就是原字符串 \(S\) 中字典序最大的子串的前缀加上这个字典序最大子串，可以发现， 这个前缀必须全由同一个字母组成，所以这一部分也可以通过 trie 计算。
顺带一提，这题的数据范围是可以出到 \(10^5\) 级别的，这时必须用 SAM 解决，但是作者不会。
以下是用 trie 树实现的代码，时间复杂度 \(O(26 \times n^2)\)：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1004535809;
const int INF=0x3f3f3f3f;
const int N=2100;
const int chn=26;#define ckmax(x,y) ( x=max(x,y) )
#define ckmin(x,y) ( x=min(x,y) )inline int read()
{int f=1,x=0; char ch=getchar();while(!isdigit(ch)) { if(ch=='-') f=-1; ch=getchar(); }while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); }return f*x;
}char s[N];
int n;
int head[chn];
int tail[chn];int T[N*N][chn];
int siz[N*N],idx;inline void Invert(int u,int i)
{if(i>n) return ;int ch=s[i]-'a';if(!T[u][ch])T[u][ch]=++idx;Invert(T[u][ch],i+1);
}inline void debug()
{for(int i=0;i<chn;i++) printf("%d ",head[i]);putchar('\n');for(int i=0;i<chn;i++) printf("%d ",tail[i]);putchar('\n');
}inline void Solve1()
{for(int i=1;i<=idx;i++) siz[i]=1;for(int i=idx;i>=0;i--)for(int j=0;j<chn;j++)if(T[i][j])siz[i]+=siz[T[i][j]];for(int i=0;i<chn;i++)if(T[0][i])head[i]=siz[T[0][i]];for(int i=1;i<=idx;i++)for(int j=0;j<chn;j++)if(!T[i][j] && T[0][j])tail[j]++;//debug();int ans=0;for(int i=0;i<chn;i++)ans=(ans+head[i]*(tail[i]+1)%mod)%mod;printf("%lld\n",ans);
}char ans[N];
int top;inline void Solve2()
{int u=0;bool flag=true;while(flag){flag=false;for(int i=chn-1;i>=0;i--)if(T[u][i]){ans[++top]=i+'a';u=T[u][i];flag=true;break;}}for(int i=1;i<=top;i++){if(i!=1 && ans[i]!=ans[i-1])break;putchar(ans[i]);}for(int i=1;i<=top;i++) putchar(ans[i]);
}signed main()
{freopen("str.in","r",stdin);freopen("str.out","w",stdout);scanf("%s",s+1),n=strlen(s+1);for(int i=1;i<=n;i++) Invert(0,i);Solve1(),Solve2();return 0;
}在附带一个教练给的用 SAM 的标程：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define REP(i,st,ed) for(int i=st,i##end=ed;i<=i##end;++i)
#define DREP(i,st,ed) for(int i=st,i##end=ed;i>=i##end;--i)
const int maxn=500005,mod=1004535809;
char s[maxn];
int len;
struct suffix_automaton{int tot,lst;int step[maxn<<1],pre[maxn<<1],ch[maxn<<1][26],c[maxn<<1];void init(){tot=lst=1;}int new_node(int lst){step[++tot]=step[lst]+1;return tot;}void expand(int x){int p=lst,np=new_node(lst);c[np]=x,lst=np;for(;(p)&&(!ch[p][x]);p=pre[p])ch[p][x]=np;if(!p)pre[np]=1;else{int q=ch[p][x];if(step[q]==step[p]+1)pre[np]=q;else{int nq=new_node(p);c[nq]=x;memcpy(ch[nq],ch[q],sizeof(ch[nq]));pre[nq]=pre[q],pre[np]=pre[q]=nq;for(;(p)&&(ch[p][x]==q);p=pre[p])ch[p][x]=nq;}}}
}s1,s2;
int head[26],tail[26];
char Max[maxn];
int Maxlen;
int main(){
#ifndef ONLINE_JUDGEfreopen("str.in","r",stdin);freopen("str.out","w",stdout);
#endifscanf("%s",s+1);len=strlen(s+1);s1.init();REP(i,1,len)s1.expand(s[i]-'a');REP(j,0,25)REP(i,2,s1.tot)if(!s1.ch[i][j])(head[j]+=s1.step[i]-s1.step[s1.pre[i]])%=mod;s2.init();DREP(i,len,1)s2.expand(s[i]-'a');REP(i,2,s2.tot)(tail[s2.c[i]]+=s2.step[i]-s2.step[s2.pre[i]])%=mod;int ans=0;REP(i,0,25)(ans+=1ll*(head[i]+1)*tail[i]%mod)%=mod;printf("%d\n",ans);int p=1;while(1){bool getnxt=0;DREP(i,25,0)if(s1.ch[p][i]){Max[++Maxlen]=i+'a';p=s1.ch[p][i];getnxt=1;break;}if(!getnxt)break;}Max[Maxlen+1]='\0';REP(i,1,Maxlen){if(Max[i]!=Max[1])break;putchar(Max[i]);}printf("%s\n",Max+1);return 0;
}