传送门

题目大意

求一个字符串的前

缀出现次数乘以长度的最大值。

题解

暴力枚举每一个前缀求出现次数再乘以常数取最大 这样做会T几个点

看了老师的做法是任意前缀出现的次数,它的next也会出现这些次数

代码

暴力

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char s[];
int nex[],len;
long long max_ans;
void getnext(){
for(int i=,j=;i<=len;i++){//从2开始啊,扎心了老铁
while(s[i]!=s[j+]&&j)j=nex[j];
if(s[i]==s[j+])nex[i]=++j;
}
}
void slove(int k){
int js=;
for(int i=,j=;i<=len;i++){
while(s[i]!=s[j+]&&j)j=nex[j];
if(s[i]==s[j+])++j;
if(j==k){
js++;j=nex[j];
}
}
// cout<<k<<" "<<js<<" "<<js*k<<endl;
max_ans=max(max_ans,(long long)js*k);
}
int main(){
ios::sync_with_stdio();
freopen("string_maxval.in","r",stdin);
freopen("string_maxval.out","w",stdout);
scanf("%s",s+);
len=strlen(s+);
getnext();
for(int i=;i<=len;i++)slove(i);
printf("%lld\n",max_ans);
return ;
}

第二种方法

#include<cstdio>
#include<iostream>
#include<cstring> using namespace std;
const int maxl=;
char s[maxl],su[maxl];
int next[maxl],l,ans=,cs[maxl];
void getnext()
{
next[]=-;
l=strlen(s);
for(int j,i=;i<l;i++)
{
j=next[i-];
while(s[i]!=s[j+]&&j>=)j=next[j];
next[i]=s[i]==s[j+]?j+:-;
}
}
int main()
{
freopen("string_maxval.in","r",stdin);
freopen("string_maxval.out","w",stdout);
scanf("%s",s);
getnext();
for(int i=l-;i>=;--i)
{
cs[i]++;
cs[next[i]]+=cs[i];
if(cs[i]*(i+)>ans)ans=cs[i]*(i+);
}
cout<<ans;
fclose(stdin);fclose(stdout);
return ;
}

最新文章

  1. 39 网络相关函数(七)——live555源码阅读(四)网络
  2. UPnP基本原理介绍
  3. Hadoop 5、HDFS HA 和 YARN
  4. Tour(KM算法)
  5. Base64 image
  6. RecyclerFullyManagerDemo【ScrollView里嵌套Recycleview的自适应高度功能】
  7. Python3.6 连接MySQL(二)转载
  8. C#退出窗体的总结方法
  9. iOS图片存在本地、再从本地获取图片
  10. HEOI2016解题报告
  11. Mac redis安装
  12. 【刷题】UOJ #374 【ZJOI2018】历史
  13. vmware虚拟机环境下配置centos为静态IP的步骤
  14. 创建Python程序
  15. Linux**系统实现log日志自动清理
  16. BZOJ4554 HEOI2016游戏
  17. iOS 功能代码 上传到 远程 码云私有库
  18. 自适应共振理论网络 ART
  19. 文本比较命令:diff
  20. 威锋网(Weiphone) BBS排序插件

热门文章

  1. vue之条件渲染
  2. windows安装RabbitMQ注意事项
  3. vSphere 6.5支持512e,NVMe SSD呢?
  4. 前端微服务-面向web平台级应用的设计
  5. 异常来自 HRESULT:0x800A01A8
  6. 使用CSS去除 去掉超链接的下划线方法
  7. 关于linter
  8. TFTP服务器
  9. hadoop2.7.1 nutch2.3 二次开发windows环境
  10. MySQL远程访问时非常慢的解决方案