#10036. 「一本通 2.1 练习 2」Seek the Name, Seek the Fame

news/2025/2/15 6:05:37/

请添加图片描述
字符串的题真的要比dfs,bfs的简单好多

大致思路

  • 首先,再度重复哈希函数 H ( C ′ ) = H ( C , k + n ) − H ( C , k ) ∗ b n H(C')=H(C,k+n)-H(C,k)*b^n H(C)=H(C,k+n)H(C,k)bn
  • 具体模板详见我的上几篇题解 哈希函数模板
  • 对此题,我们只需要对字符串计算哈希函数值枚举可能的前后缀长度即可。
bool check(ull len,ull nlen){if(ahash[len]==ahash[nlen]-ahash[nlen-len]*poww[len]){return 1;}return 0;
}
while(scanf("%s",s+1)!=EOF)//两种多组输入模式//while(cin>>s+1){ahash[0]=0;int n=strlen(s+1);for(int i=1;i<=n;i++){ahash[i]=(s[i]+ahash[i-1]*b);}for(ull i=1;i<=n;i++){if(check(i,n)==1){cout<<i<<" ";}}cout<<endl;}
  • 假设主串长度为N,子串长度为K,则前缀哈希值等于 h a s h [ K ] hash[K] hash[K],后缀的哈希值等于 h a s h [ N ] − h a s h [ N − K ] ∗ b K hash[N]-hash[N-K]*b^K hash[N]hash[NK]bK
  • 显然,若前者等于后者,则是合法的。

AC CODE

#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int N=1e6+9;
char s[N],s2[N];
int b=11,h=100000009,n;
ull poww[N],ahash[N];
bool check(ull len,ull nlen){if(ahash[len]==ahash[nlen]-ahash[nlen-len]*poww[len]){return 1;}return 0;
}
int main(){poww[0]=1;for(int i=1;i<=1000000;i++){poww[i]=poww[i-1]*b;}while(scanf("%s",s+1)!=EOF)//while(cin>>s+1){ahash[0]=0;int n=strlen(s+1);for(int i=1;i<=n;i++){ahash[i]=(s[i]+ahash[i-1]*b);}for(ull i=1;i<=n;i++){if(check(i,n)==1){cout<<i<<" ";}}cout<<endl;}return 0;
}

附上封面

请添加图片描述


http://www.ppmy.cn/news/540228.html

相关文章

台式计算机idc数据排名,IDC:2018年全球个人计算设备出货量约为4.07亿台 下滑大约3.9%...

IDC日前公布了2018年个人计算设备(Personal Computing Devices)及2022年的预测报告&#xff0c;这里说的个人计算设备是广义上的&#xff0c;包括桌面电脑、笔记本电脑、变形平板及直板平板电脑四大类。从IDC的报告来看&#xff0c;2018年全球个人计算设备出货量约为4.07亿台&a…

Windows和Linux销量,Windows 7和Linux,谁才是Netbook市场的霸主?

根据BNP Paribas的预测&#xff0c;在未来一年内上网本的销售量将增长60%&#xff0c;而笔记本仅增长18%。目前全球几大著名PC厂商&#xff0c;包括华硕、戴尔、惠普和宏碁等都纷纷 推出了自己的上网本&#xff0c;预装的操作系统一般是Windows XP、Ubuntu Linux或其它Linux系统…

芯片市场对中国5G手机出货量月度计算

芯片一级代理商&#xff1a;芯片代理商月度计算中国5G手机出货量出货量大幅增加&#xff0c;突破了前几年出货量低增加的瓶颈。2020年全球笔记本电脑出货量将到达2.01亿台&#xff0c;同比增加20%以上&#xff0c;平板电脑出货量在疫情前后也有明显增加。后疫情时代&#xff0c…

全球计算机出货量排名,2017年全球PC出货量分析:全年出货量达2.6亿台

据数据显示&#xff0c;全球PC出货量依然在下滑&#xff0c;而IDC的则表示2017年第四季度PC出货量出现了正增长&#xff0c;是2011年以来增长最稳定的一年。 Gartner估计&#xff0c;全球PC出货量在2017年第四季度环比下滑2.0%至7155万台&#xff0c;第四季度PC出货量排名前6的…

2020年BOE(京东方)柔性折叠OLED屏出货量位居全球第二

随着全球品牌手机厂商相继发布折叠屏手机产品规划&#xff0c;当前市场对于折叠、卷曲等新形态显示产品需求的持续升温。群智咨询&#xff08;Sigmaintell&#xff09;数据显示&#xff0c;2020年&#xff0c;全球柔性智能手机折叠面板&#xff0c;BOE&#xff08;京东方&#…

计算机销量,工信部:去年中国计算机出货量占全球90.6%

本报讯(记者祝剑禾)昨天&#xff0c;工信部发布《2011年电子信息产业统计公报》&#xff0c;在2011年&#xff0c;我国彩电、手机、计算机等主要电子产品产量占全球出货量的比重分别达到48.8%、70.6%和90.6%&#xff0c;均名列世界第一。 工业支柱地位凸显 根据工信部的统计数据…

全球计算机设备数量统计,IDC:2018年全球个人计算设备出货量约为4.07亿台 下滑大约3.9%...

原标题&#xff1a;IDC&#xff1a;2018年全球个人计算设备出货量约为4.07亿台 下滑大约3.9% 传统PC市场今年Q2季度曾出现过短暂复苏&#xff0c;不论IDC还是盖特纳的数据都显示PC出货量增长了&#xff0c;尽管涨幅只有1%、2%&#xff0c;但这已经是六年来PC市场首次增长了。但…

希捷上季度硬盘出货量4590万部,好日子也不复返了

西数上周发布了2016年Q2财报&#xff0c;营收、利润双双下跌&#xff0c;HDD硬盘出货量也只有4968万部&#xff0c;是这两年来的历史第二低。西数保住了HDD硬盘市场第一的位置&#xff0c;因为面对HDD这个鸟样&#xff0c;希捷的日子也没好过到哪里去——截至接年1月1日的2016财…