#10046. 「一本通 2.2 练习 2」OKR-Periods of Words(内附封面)

news/2024/2/21 3:09:56

[POI2006] OKR-Periods of Words

题面翻译

对于一个仅含小写字母的字符串 a a a p p p a a a 的前缀且 p ≠ a p\ne a p=a,那么我们称 p p p a a a 的 proper 前缀。

规定字符串 Q Q Q(可以是空串)表示 a a a 的周期,当且仅当 Q Q Q a a a 的 proper 前缀且 a a a Q + Q Q+Q Q+Q 的前缀。

例如 ababab 的一个周期,因为 ababab 的 proper 前缀,且 ababab+ab 的前缀。

求给定字符串所有前缀的最大周期长度之和。

题目描述

A string is a finite sequence of lower-case (non-capital) letters of the English alphabet. Particularly, it may be an empty sequence, i.e. a sequence of 0 letters. By A=BC we denotes that A is a string obtained by concatenation (joining by writing one immediately after another, i.e. without any space, etc.) of the strings B and C (in this order). A string P is a prefix of the string !, if there is a string B, that A=PB. In other words, prefixes of A are the initial fragments of A. In addition, if P!=A and P is not an empty string, we say, that P is a proper prefix of A.

A string Q is a period of Q, if Q is a proper prefix of A and A is a prefix (not necessarily a proper one) of the string QQ. For example, the strings abab and ababab are both periods of the string abababa. The maximum period of a string A is the longest of its periods or the empty string, if A doesn’t have any period. For example, the maximum period of ababab is abab. The maximum period of abc is the empty string.

Task Write a programme that:

reads from the standard input the string’s length and the string itself,calculates the sum of lengths of maximum periods of all its prefixes,writes the result to the standard output.

输入格式

In the first line of the standard input there is one integer k k k ( 1 ≤ k ≤ 1 000 000 1\le k\le 1\ 000\ 000 1k1 000 000) - the length of the string. In the following line a sequence of exactly k k k lower-case letters of the English alphabet is written - the string.

输出格式

In the first and only line of the standard output your programme should write an integer - the sum of lengths of maximum periods of all prefixes of the string given in the input.

样例 #1

样例输入 #1

8
babababa

样例输出 #1

24

数据范围与提示

对于全部数据, 1 < k < 1 0 6 1\lt k\lt 10^6 1<k<106

人话翻译:

给定一个字符串A,求他所有前缀B(包括A=B)的最大周期,周期即B的前缀C最长,C要满足B是CC的字串。实例:
A B A B A B A B 的所有前缀有: − − − − − − − − − 周期为 − − − 长度 ABABABAB的所有前缀有:---------周期为---长度 ABABABAB的所有前缀有:周期为长度
A − − − − − − − − − − − − − − − − − − − − 无 − − − − − 0 A--------------------无-----0 A0
A B − − − − − − − − − − − − − − − − − − − 无 − − − − − 0 AB-------------------无-----0 AB0
A B A − − − − − − − − − − − − − − − − − − A B − − − − − 2 ABA------------------AB-----2 ABAAB2
A B A B − − − − − − − − − − − − − − − − − A B − − − − − 2 ABAB-----------------AB-----2 ABABAB2
A B A B A − − − − − − − − − − − − − − − − A B A B − − − − 4 ABABA----------------ABAB----4 ABABAABAB4
A B A B A B − − − − − − − − − − − − − − − A B A B − − − − 4 ABABAB---------------ABAB----4 ABABABABAB4
A B A B A B A − − − − − − − − − − − − − − A B A B A B − − − 6 ABABABA--------------ABABAB---6 ABABABAABABAB6
A B A B A B A B − − − − − − − − − − − − − A B A B A B − − − 6 ABABABAB-------------ABABAB---6 ABABABABABABAB6
因此输出结果为 2 + 2 + 4 + 4 + 6 + 6 = 24 因此输出结果为2+2+4+4+6+6=24 因此输出结果为2+2+4+4+6+6=24

怎么求这些周期长度呢?KMP的精髓也在此,附图(其中next数组就是之前模板中提到的p数组,含义是相同的)

在这里插入图片描述

明显其中的蓝线是黑线的周期

那么这个题目就变得极其简单了,只需要求出 i − n e x t [ n e x t [ i ] ] i-next[next[i]] inext[next[i]],ans累加即可

很简单就可以得到实现代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+999;
int p[N],n,len,ans=0;
char a[N];
void pre(){//KMP模板int j=0;p[1]=0;for(int i=1;i<n;i++){while(j>0&&a[i+1]!=a[j+1])j=p[j];if(a[i+1]==a[j+1])j++;p[i+1]=j;}
} 
int main(){cin>>n;scanf("%s",a+1);pre();for(int i=1;i<=n;i++){int j=i;while(p[j])j=p[j];ans+=i-j;}cout<<ans;return 0;
} 

但是!这样是不够的,会得到以下结果

在这里插入图片描述

算法原理是肯定没有错的,但是问题在哪?

注意k的范围

对于全部数据, 1 < k < 1 0 6 1\lt k\lt 10^6 1<k<106
那么对于我们在累加的ans可能会超出int的范围

十年OI一场空,不开long long 见祖宗

加上longlong

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+999;
int p[N],n;
long long int ans=0;
char a[N];
void pre(){int j=0;p[1]=0;for(int i=1;i<n;i++){while(j>0&&a[i+1]!=a[j+1])j=p[j];if(a[i+1]==a[j+1])j++;p[i+1]=j;}
} 
int main(){cin>>n;scanf("%s",a+1);pre();for(int i=1;i<=n;i++){int j=i;while(p[j])j=p[j];if(p[i]!=0)p[i]=j; ans+=i-j;}cout<<ans;return 0;
} 

信心十足的交上代码,

在这里插入图片描述

哎?不是,啊?KMP超时了?FFFF

咳,随着数据变大,查找 n e x t [ n e x t [ ] ] next[next[]] next[next[]]的时间就变得难以接受,我们可以通过记忆化的方式更改 n e x t next next数组,原理类似于并查集的优化

实现代码(AC)

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+999;
int p[N],n;
long long int ans=0;
char a[N];
void pre(){int j=0;p[1]=0;for(int i=1;i<n;i++){while(j>0&&a[i+1]!=a[j+1])j=p[j];if(a[i+1]==a[j+1])j++;p[i+1]=j;}
} 
int main(){cin>>n;scanf("%s",a+1);pre();for(int i=1;i<=n;i++){int j=i;while(p[j])j=p[j];if(p[i]!=0)p[i]=j;//记忆化,否则会有TLE。 ans+=i-j;}cout<<ans;return 0;
} 

附封面

请添加图片描述


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

相关文章

Web页面实现打印功能

核心的代码&#xff1a; window.print() 具体的实现如下&#xff1a; <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns"http://www.w3.org/199…

Jquery网页打印

今天做项目中&#xff0c;需要用到打印功能&#xff0c;开始的时候用js来调用打印机&#xff0c;之后样式&#xff0c;还有什么的都没有了&#xff0c;之后ie有时候还运行不了&#xff0c;后来就在网上找&#xff0c;之后发现jquery有打印插件&#xff0c;所以就用了&#xff0…

网页打印非常优秀的插件 Print.js

前言&#xff1a;最近需要在网页上打印&#xff0c;网上找了很多&#xff0c;刚开始使用的 lodop打印插件来打印&#xff0c;没有达到理想的要求&#xff0c;它需要下载、区分浏览器的位数来安装、在vue使用时候必须写成内部样式&#xff0c;在笔记本样式失效等问题&#xff0c…

html页面实现打印功能

html页面实现打印功能 可用代码效果截图 之前领导让我写一个html页面&#xff0c;可以进行打印&#xff0c;我上网搜了一下&#xff0c;html页面实现打印功能的博客有很多&#xff0c;这里我就不一一介绍了&#xff0c;直接上干货。 可用代码 <!DOCTYPE html> <html …

前端页面打印功能

1.需求介绍 本项目为vue项目&#xff0c;审批表页面需要添加打印功能&#xff0c;打印区域由3部分组成&#xff08;标题、表格和签名&#xff09; 2.为什么不使用PrintJS 一开始我们使用的是printJS() printDetail() {printJS({printable:printJS-form, //打印区域type:html…

Web打印

布鲁斯李 Web打印 随着10i新版本的发布&#xff0c;在10i的iserver中&#xff0c;内置了一个web打印服务。是指将您在 Web 应用中制作的 Web 内容输出为可打印的文档。那么如何使用该服务&#xff0c;请继续往下看&#xff1a; 执行一次成功的web打印任务&#xff0c;我们需要…

html页面实现打印

html页面实现打印功能 方式一 打印整个html页面方式二 通过获取页面html内容打印 方式一 打印整个html页面 <!DOCTYPE html> <html lang"zh" xmlns:th"http://www.thymeleaf.org" > <head><th:block th:include"include :: hea…

WEB打印-网页打印功能(带分页、可多页打印)

<html> <head> <title>Web打印</title> <meta http-equiv"Content-Type" content"text/html; charsetgb2312"> <!--mediaprint 这个属性可以在打印时有效--> <style mediaprint> .Noprint{display:…

前端打印网页

文章目录 CSS控制局部打印例子网页加水印&#xff0c;而打印时不加水印参考文献 打印网页&#xff0c;可以调用window.print()方法。该方法会打印出当前网页。 现在你就可以打开控制台&#xff0c;尝试一哈 运行结果 &#xff1a; 当然&#xff0c;可以控制哪些元素不被打印 &…

前端网页打印window.print()

前言 print作为浏览已经比较成熟的技术可以经常被用来打印页面的部分内容&#xff0c;我们可以在MDN上查看到相关的简单介绍。 一、print()方法 print() 方法用于打印当前窗口的内容。调用 print() 方法会产生一个打印预览弹框&#xff0c;让用户可以设置打印请求。最简单的打…

前端网页打印插件print.js

在前端开发中&#xff0c;想打印当前网页的指定区域内容&#xff0c;或将网页导出为多页的PDF&#xff0c;可以借助print.js实现&#xff0c;该插件轻量、简单、手动引入、不依赖其他库。示范项目github&#xff1a;https://github.com/lemoncool/print-demo。打印或导出PDF后效…

简单实用的web打印方案-网页精准打印

在当前这个互联网时代&#xff0c;大部分企业都搭建了自已的平台&#xff0c;通过平台联系客户&#xff0c;与粉丝互动&#xff0c;展示自己的产品。PC网站、APP、手机站、这些平台是企业互联网生态系统的重要基础。在公司平台化、系统化的今天&#xff0c;工作中出现web打印的…

web打印的几种方法(2023)

在工作中出现web打印的情况是非常多的&#xff0c;其实这也是一个比较烦人的问题&#xff0c;这篇博客整理一下关于Web打印的一些方法或者方式。 1. window.print() 这个方法是用来打印网页的&#xff0c;页面上的其他的元素也会被打印处理&#xff0c;在打印的时候页眉页脚是…

网页实现打印功能

在JavaScript中&#xff0c;可以使用Window对象的print()方法来实现打印操作&#xff0c;语法格式“window.print()”。print()方法用于打印当前窗口的内容&#xff1b;调用print()方法会产生一个打印预览弹框&#xff0c;让用户可以设置打印请求。 打印当前页面指定元素中的内…

python实现削苹果小游戏

也不用998只有199源码发你。 支付完发我邮箱发你源代码。

MongoDB的文档操作

在MongoDB中文档是指多个键及其关联的值有序地放置在一起就是文档&#xff0c;其实指的就是数据&#xff0c;也是我们平时操作最多的部分。 MongoDB中的文档的数据结构和 JSON 基本一样。所有存储在集合中的数据都是 BSON 格式。 BSON 是一种类似 JSON 的二进制形式的存储格式&…

AppID登陆

打开开发者网站 http://developer.apple.com/ 登上开发者账号 找到应用程序的ID 如果是新的应用 直接在新建应用的时候勾选上&#xff08;新建过得编辑然后勾选&#xff09; Sign In with Apple 如图 然后用Xcode打开或者新建的项目 添加AuthenticationServices.framew…

苹果账户登录_iOS 13的通过 Apple 登录第三方应用

在 iOS 13多了一个Sign in with Apple&#xff0c;就是苹果账号登录&#xff0c;通过苹果账户来第三方登录&#xff0c;例如微信、QQ、微博的快速登录&#xff0c;那么是否有那么神奇呢。 通过 Apple 登录 使用 Apple ID 设置和登录帐户&#xff0c;您无需填表或者创建并记住新…

开源IDaaS方舟一账通ArkID系统内置OIDC 认证插件配置流程

OIDC 是基于OAuth2和OpenID整合的新身份认证授权标准协议&#xff0c;且完全兼容 OAuth。Access Token 来解决授权第三方客户端访问受保护资源的问题&#xff0c;OIDC 在这个基础上提供了ID Token 来解决第三方客户端标识用户身份认证的问题。开源IDaaS方舟一账通ArkID系统内置…

Sign in With Apple (苹果授权登录)

Sign in With Apple &#xff08;苹果授权登录&#xff09; 关于Sign in With Apple &#xff08;苹果授权登录&#xff09;的问题&#xff0c;公司app上架appStore被拒原因是使用第三方授权登陆但是却没有使用苹果账号的授权登陆&#xff0c;苹果强制要求涉及到第三方登陆的a…
最新文章