当前位置: 首页 > news >正文

解题报告-字符串(str.*)

字符串(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;
}
http://www.hskmm.com/?act=detail&tid=16161

相关文章:

  • Linux 系统中的 /dev/disk/by-id/目录作用详解
  • glTF/glb:您需要知道的一切,怎么免费获取下载
  • keepalived服务器
  • P8818 [CSP-S 2022] 策略游戏
  • FortiGate连接中国联通SDWAN
  • 第五章 运算符、表达式和语句
  • 学习问题日记-2
  • 封神台复现
  • 李之一的Java第一作
  • 2025.9.24 闲话:Lucas 定理究极证明
  • Are English people good or bad
  • 9
  • Lampiao靶场渗透wp-脏牛提权
  • 画矩形
  • NOIP 模拟赛八
  • 第三篇
  • 基于cloacked-pixel隐写工具爆破项目
  • 随便写的
  • Bcliux-docker-nacos2.2.0升级至2.2.3版本
  • 社交网络架构。京东场景题:亿级用户100Wqps 社交关系如何设计?如何查看我的关注,关注我的?
  • go 面试题
  • 事件和图形界面(暂未完成)
  • 什么是sql 慢日志。哈罗面试:没开sql慢日志,怎么发现慢 sql?
  • Spring连环炮。哈罗面试:Spring Bean生命周期,Spring怎么创建Bean的,BFPP和BPP的x别
  • redis 大 key 优化。哈罗面试:redis 有个大 key需要在线优化, 不能影响现有业务,请求不能大量到库,怎么优化?
  • ACL高可用架构。希音面试:第三方挂了,我们总在背锅。来一 靠谱的 高可用方案,让 外部依赖 稳如泰山
  • 软工9.24
  • 2025CSP-S模拟赛51
  • 2025年9月24日 - 20243867孙堃2405
  • 【星海随笔】RabbitMQ开发篇 - 教程