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

news/2024/2/21 10:33:43

请添加图片描述
字符串的题真的要比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财…

商用计算机idc市场排名,IDC 2019 年中国 PC 市场十大预测:出货量约 5060 万台

12 月 27 日&#xff0c;IDC 发布 2019 年中国 PC 市场十大预测。IDC 指出&#xff0c;2018 年全年中国 PC 市场预计最终销售为 5200 万台左右&#xff0c;下滑了 3.4%。2019 年中国 PC 市场会处于一种习惯性艰难期&#xff0c;但是市场也不乏一些重要的机会点。 IDC 预测&…

计算机常见的智能终端有哪些,2019年中国智能终端行业市场规模,及主要细分领域出货量情况 [图]...

智能终端即移动智能终端的简称。移动智能终端拥有接入互联网能力&#xff0c;通常搭载各种操作系统&#xff0c;可根据用户需求定制化各种功能。生活中常见的智能终端包括&#xff0c;智能收入、平板电脑、笔记本、可穿戴设备、车载智能终端等。 移动智能终端主要产品 资料来源…

2020年全球及中国显示驱动芯片行业产业链、出货量及竞争格局分析「图」

一、显示驱动芯片行业定义及产业链 1、定义 显示驱动芯片是显示面板成像系统中的重要组成部分&#xff0c;芯片集成了电阻、调节器、比较器和功率晶体管等部件&#xff0c;控制着显示面板的发光线性度、功率、电磁兼容等关键因素&#xff0c;从而保证显示画面的均匀性和稳定性…

Gartner:2015年第四季度全球PC出货量下滑8.3%

根据全球领先的信息技术研究和顾问公司Gartner的初步统计结果&#xff0c;2015年第四季度全球个人电脑&#xff08;PC&#xff09;出货量达7,570万台&#xff0c;较2014年第四季度下滑8.3%。全年PC出货量为2.887亿台&#xff0c;较2014年下滑8%。 Gartner首席分析师北川美佳子&…

计算机整机制造业下滑,多因素导致全球PC出货量下滑 中国增速减缓

2013年全球PC需求下滑&#xff0c;中国PC增速减缓 全球来看&#xff0c;2013年&#xff0c;全球PC出货量同比下降10.66%&#xff0c;出货量仅为3.15亿台&#xff0c;创下有史以来最大跌幅。其中&#xff0c;平板电脑增势喜人&#xff0c;但还是出现明显放缓迹象。2013年全球平板…

平板出货量

据市场研究机构IDC发布数据&#xff0c;2012年4-6月份&#xff0c;全球平板电脑的总出货量为2499万台&#xff0c;同比增长66%。其中苹果公司iPad出货量为1704万台&#xff0c;同比增长84%&#xff0c;全球市占率达到了68.2%。IDC预测&#xff0c;2012年全年平板电脑出货量可达…

《Python自动化测试九章经》

Python是当前非常流行的一门编程语言&#xff0c;它除了在人工智能、数据处理、Web开发、网络爬虫等领域得到广泛使用之外&#xff0c;他也非常适合软件测试人员使用&#xff0c;但是&#xff0c;对于刚入行的测试小白来说&#xff0c;并不知道学习Python语言可以用来完成哪些测…

数据清洗以及常用的方法

最近用到数据清洗&#xff0c;写篇博客&#xff0c;供自己回忆&#xff0c;供有需要的人参考~ 一、数据清洗是什么&#xff1f; 数据清洗&#xff0c;顾名思义就是将要用到的数据中重复、多余部分的数据进行筛选并清除&#xff1b;把缺失部分补充完整&#xff0c;并将不正确的…

如何做数据清洗?

一.预处理阶段 预处理阶段主要做两件事情&#xff1a; 一是将数据导入处理工具。通常来说&#xff0c;建议使用数据库&#xff0c;单机跑数搭建MySQL环境即可。如果数据量大&#xff08;千万级以上&#xff09;&#xff0c;可以使用文本文件存储python操作的方式 而是看数据…

数据清洗概述

一、简介 1、简介 大数据时代&#xff0c;必须经过清洗、分析、建模、可视化才能体现其价值&#xff0c;然后众多数据中总是存在很多“脏数据”&#xff0c;也就是不完整、不规范、不准确的数据&#xff0c;数据清洗就是指将“脏数据”洗掉&#xff0c;包括检查数据一致性&…

数据清洗

数据清洗的概念 数据清洗的流程 字段选择 数据质量报告 数据清洗主要工作 数据清洗的概念 数据清洗主要是针对数据中的错误值、异常值、缺失值进行处理的过程&#xff0c;以及删除那些取值很多的类别型字段&#xff0c;或者取值一致性程度极高的字段。 数据清洗流程 1.再次确…

数据清洗是什么

数据清洗是什么 数据清洗就是指发现并纠正数据文件中可识别的错误的最后一道程序&#xff0c;包括检查数据一致性&#xff0c;处理无效值和缺失值等。 数据清洗规则 数据清洗有四个关键点。 完整性 单条数据是否存在空值&#xff0c;统计的字段是否完善 全面性 观赏某一…
最新文章