LUOGU P3435 [POI2006]OKR-Periods of Words
2024-09-08 00:32:16
解题思路
首先求出kmp,那么i-nxt[i]一定是一个周期,对于每一个点一直跳nxt,跳到最小的nxt之后用i-这个nxt即为i这个前缀的答案。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
using namespace std;
const int MAXN = 1000005;
int nxt[MAXN],n;
long long ans;
char s[MAXN];
int main(){
scanf("%d%s",&n,s+1);
for(register int i=2,j=0;i<=n;i++){
while(j && s[i]!=s[j+1]) j=nxt[j];
if(s[i]==s[j+1]) j++;
nxt[i]=j;
}
// for(register int i=1;i<=n;i++) cout<<nxt[i]<<" ";
for(register int i=1;i<=n;i++){
int j=i;
while(nxt[j]) j=nxt[j];
if(nxt[i]) nxt[i]=j;
ans+=i-j;
}printf("%lld",ans);
return 0;
}
最新文章
- PHP 正则表达式匹配中文字符
- Qt之Qprocess
- Node.js学习笔记(1)
- Git diff (---和+++具体解释)
- 450A - Jzzhu and Children 找规律也能够模拟
- Ajax交互,浏览器接收不到服务器的Json数据(跨域问题)
- js中的简单数据类型和复杂数据类型的存储
- IntelliJ IDEA 破解Jrebel6.3.0安装
- LeetCode算法题-Rotate Array(Java实现)
- git 冲突解决的方法
- 安装cx_Oracle 6
- RSA/SHA1加密和数字签名算法在开放平台中的应用
- 作为sort()方法的参数的比较函数(高程三第五章)
- JAVAWEB 一一 userweb2(升级,servlet版,jstl和el)
- MySQL 中的数据类型介绍(转)
- 使用js 文件参数 以及IHttpModule实现服务验证asp.net 版的初步实现
- 红帽RHOP 8 发布一条龙方案
- 文本情感分类:分词 OR 不分词(3)
- Pythone3 sys模块
- 【JeeSite】区域和菜单管理
热门文章
- java笔试之提取不重复的整数
- 2-sat——输出方案poj3683
- Clion IDE的安装
- sql不用拼接语句实现动态查询条件
- js中的继承和重载
- 解析Request和Response
- Swagger发布服务器时错误 500 : { ";Message";: ";An error has occurred."; }
- C++【vector】用法和例子
- C++【string】用法和例子
- Python PIL 怎么知道写入图片格式的kb大小