[51nod 1129] 字符串最大值(kmp)
2024-08-28 22:42:03
题目大意
求一个字符串的前
缀出现次数乘以长度的最大值。
题解
暴力枚举每一个前缀求出现次数再乘以常数取最大 这样做会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 ;
}
最新文章
- 39 网络相关函数(七)——live555源码阅读(四)网络
- UPnP基本原理介绍
- Hadoop 5、HDFS HA 和 YARN
- Tour(KM算法)
- Base64 image
- RecyclerFullyManagerDemo【ScrollView里嵌套Recycleview的自适应高度功能】
- Python3.6 连接MySQL(二)转载
- C#退出窗体的总结方法
- iOS图片存在本地、再从本地获取图片
- HEOI2016解题报告
- Mac redis安装
- 【刷题】UOJ #374 【ZJOI2018】历史
- vmware虚拟机环境下配置centos为静态IP的步骤
- 创建Python程序
- Linux**系统实现log日志自动清理
- BZOJ4554 HEOI2016游戏
- iOS 功能代码 上传到 远程 码云私有库
- 自适应共振理论网络 ART
- 文本比较命令:diff
- 威锋网(Weiphone) BBS排序插件