【bzoj1511】[POI2006]OKR-Periods of Words KMP-next数组
2024-08-27 21:21:02
原文地址:http://www.cnblogs.com/GXZlegend/p/6827027.html
题目描述
一个串是有限个小写字符的序列,特别的,一个空序列也可以是一个串. 一个串P是串A的前缀, 当且仅当存在串B, 使得 A = PB. 如果 P A 并且 P 不是一个空串,那么我们说 P 是A的一个proper前缀. 定义Q 是A的周期, 当且仅当Q是A的一个proper 前缀并且A是QQ的前缀(不一定要是proper前缀). 比如串 abab 和 ababab 都是串abababa的周期. 串A的最大周期就是它最长的一个周期或者是一个空串(当A没有周期的时候), 比如说, ababab的最大周期是abab. 串abc的最大周期是空串. 给出一个串,求出它所有前缀的最大周期长度之和.
输入
第一行一个整数 k ( 1 k 1 000 000) 表示串的长度. 接下来一行表示给出的串.
输出
输出一个整数表示它所有前缀的最大周期长度之和.
样例输入
8
babababa
样例输出
24
题目大意
定义A串为B串的循环串,当且仅当A是B的前缀(不包括B本身),且B为连续的A串拼接的字符串的前缀。给出一个字符串,求它的所有前缀(包括本身)的最长循环串的长度之和。
题解
KMP-next数组
最长循环串长度=总长度-最短相同前后缀长度
求最短相同前后缀长度,根据next数组的定义:最长相同前后缀长度,可以一直取next,直到不能取为止,得到最短相同前后缀长度。
这样极限时间复杂度是O(n^2)。
我们可以想到:每次求完1次next之后的部分已经在之前求过,可以储存下来,下一次直接用。时间复杂度O(n)。
#include <cstdio>
char str[1000010];
int next[1000010] , cnt[1000010];
int main()
{
int n , i = 0 , j = -1;
long long ans = 0;
scanf("%d%s" , &n , str);
next[0] = -1;
while(i < n)
{
while(~j && str[j] != str[i]) j = next[j];
i ++ , j ++ , next[i] = j;
}
for(i = 1 ; i <= n ; i ++ )
{
if(next[i] != 0) cnt[i] = cnt[next[i]];
else cnt[i] = i;
ans += i - cnt[i];
}
printf("%lld\n" , ans);
return 0;
}
最新文章
- 关于jQuery中环境配置中的问题
- 【接口测试】jmeter的使用
- setTimeout
- 老王Python培训视频教程(价值500元)【基础进阶项目篇 &ndash; 完整版】
- div元素呈圆环排列
- WRS是什么?
- bzoj2186
- .net mvc结合微软提供的FormsAuthenticationTicket登陆
- asp.net webform生命周期
- jquery_核心_(1)
- java Script 用if else 实现从大到小指定输出,升序排列
- iOS 应用提交到iTunes Connect,显示";正在处理";后消失不见
- C++ WMI获取系统硬件信息(CPU/DISK/NetWork etc)
- JavaEE 之 Mybatis
- jumpserver堡垒机web终端支持复制粘贴功能
- Redis入门到高可用(八)——list
- vsftpd下错误之:500 OOPS
- Elasticsearch学习之ES节点类型以及各种节点的分工
- Spring boot Security 用于权限管理,用户添加等。
- yii2 restful api——app接口编程实例
热门文章
- Ajax (Asynchronous javascript xml) 搜索框核心代码(JQuery) Ajax判断用户名存在核心代码 附:原生js的Ajax代码 其中有json的一句话解释
- jquery动态改变元素内容
- vue数据绑定html
- 在唯一密钥属性“fileExtension”设置为“.”时,无法添加类型为“mimeMap”的重复集合项
- 怎样通过互联网ssh访问家里电脑
- Numpy安装报错:试过N种安装方法终于
- Choosing Capital for Treeland CodeForces - 219D (树形DP)
- 使用python制作神经网络——搭建框架
- No module named appium
- Kettle资源库配置(数据库资源库和文件资源库)