关键词：
原文地址：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;
}
1511:[poi2006]okr-periodsofwords(代码片段)
1511:[POI2006]OKR-PeriodsofWordshttps://www.lydsy.com/JudgeOnline/problem.php?id=1511 题意： 对于一个串的所有前缀，设为s，求出它的最大前缀Q，使得s为QQ的前缀。求最大前缀长度的和。分析： KMP+next数组。 next数组表示的是这个字... 查看详情
bzoj1520poi2006szk-schools
1520:[POI2006]Szk-SchoolsTimeLimit: 5Sec MemoryLimit: 64MBSubmit: 771 Solved: 398[Submit][Status][Discuss]DescriptionInputOutput如果有可行解,输出最小代价,否则输出NIE.SampleIn 查看详情
bzoj1520[poi2006]szk-schoolskm算法
【BZOJ1520】[POI2006]Szk-SchoolsDescriptionInputOutput如果有可行解,输出最小代价,否则输出NIE.SampleInput5112311513255415103331SampleOutput9题解：二分图最小权匹配裸题，可以直接无脑费用流，不过这里就当复习一下KM算法了。#include<cstdio>#inclu... 查看详情
bzoj1510[poi2006]kra-thedisks*
bzoj1510[POI2006]Kra-TheDisks题意：一个瓶子有n个节，每个节有一个宽度。现在要从上往下扔m个盘子，如果盘子的下一个位置宽度比该盘子的宽度小则盘子会停在这个位置。问最后一个盘子会停在那个位置。n，m≤300000。题解：首先利... 查看详情
[bzoj1510][poi2006]kra-thedisks_暴力
Kra-TheDisksbzoj-1510POI-2006题目大意：题目链接。注释：略。想法：不难发现其实只有前缀最小值是有效的。进而我们把盘子一个一个往里放，弄一个自底向上的指针往上蹦即可。时间复杂度$O(n)$。Code：#include<iostream>#include<cst... 查看详情
[bzoj1513][poi2006]tet-tetris3d
[BZOJ1513][POI2006]Tet-Tetris3D试题描述Task:Tetris3D"Tetris"游戏的作者决定做一个新的游戏,一个三维的版本,在里面很多立方体落在平面板,一个立方体开始落下直到碰上一个以前落下的立方体或者落地即停止.作者想改变一下游戏的目的使... 查看详情
bzoj1513:[poi2006]tet-tetris3d
Description三维空间从上落下几个长方体,问最后的最高高度.Solution二维线段树.感觉这种东西是可以yy出来的吧..对行建线段树,再对列建线段树维护行的信息,注意打标记的位置,和返回的时候一定要记得统计上标记.开4倍内存会MLE...Co... 查看详情
bzoj1513[poi2006]tet-tetris3d二维线段树
【BZOJ1513】[POI2006]Tet-Tetris3DDescriptionTask:Tetris3D"Tetris"游戏的作者决定做一个新的游戏,一个三维的版本,在里面很多立方体落在平面板,一个立方体开始落下直到碰上一个以前落下的立方体或者落地即停止.作者想改变一下游戏的目的... 查看详情
bzoj1513[poi2006]tet-tetris3d(代码片段)
二维线段树板子，注意标记永久化。1#include<bits/stdc++.h>2usingnamespacestd;3intans,A,B,n,ql,qr,qd,qu;4structQuerx56intv[3005],tag[3005];7voidchange(intk,intl,intr,intL,intR,intw)89v[k]=max(v[k],w);10if(l==L&a 查看详情
bzoj1520[poi2006]szk-schools费用流
题目描述输入输出如果有可行解,输出最小代价,否则输出NIE.样例输入5112311513255415103331样例输出9题解费用流设xi表示学生，yi表示编号，那么S->xi，容量为1，费用为0；xi->能够使得xi接受的yj，容量为1，费用为按照题目中计算... 查看详情
bzoj1513[poi2006]tet-tetris3d二维线段树
题目链接BZOJ1513题解真正地理解了一波线段树标记永久化的姿势每个节点维护两个值\(v\)和\(tag\)\(v\)代表儿子中的最值\(tag\)代表未下传的最值显然节点的区间大于等于\(v\)的实际区间而\(tag\)的区间包含节点的区间我们在修改的时... 查看详情
bzoj1513:[poi2006]tet-tetris3d
DescriptionTask:Tetris3D"Tetris"游戏的作者决定做一个新的游戏,一个三维的版本,在里面很多立方体落在平面板,一个立方体开始落下直到碰上一个以前落下的立方体或者落地即停止.作者想改变一下游戏的目的使得它更大众化,在新游戏... 查看详情
bzoj1513[poi2006]tet-tetris3d（二维线段树）
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=1513 【题目大意】 一个立方体开始落下直到碰上一个以前落下的立方体或者落地即停止. 你将知道落下的立方体信息以及位置, 你的任务就是回答所有立方... 查看详情
bzoj1515[poi2006]lis-thepostman有向图欧拉回路(代码片段)
LINK：Lis-ThePostman看完题觉得虽然容易发现是有向图欧拉回路但是觉得很难解决这个问题。先分析一下有向图的欧拉回路：充要条件图中每个点的入度-出度=0且整张图是一个强连通分量。证明：首先考虑前者这个思想是从一个点出... 查看详情
[poi2006]ork-ploughing
[POI2006]ORK-Ploughinghttps://www.luogu.org/problemnew/show/P3444题目描述(Byteasar)想耕种他那块矩形的田,他每次能耕种矩形的一边(上下左右都行),在他每次耕完后,剩下的田也一定是矩形,每块小区域边长为(1),耕地的长宽分别为(m)和(n),不幸的是(... 查看详情
bzoj2428:[haoi2006]均分数据
二次联通门: BZOJ2428:[HAOI2006]均分数据 /*BZOJ2428:[HAOI2006]均分数据模拟退火初体验完全随机化算法估计对我这种非酋来说的话估计是用处不大了吧23333*/#include<cstdio>#include<iostream>#include<cstdlib>#incl 查看详情
[bzoj2527][poi2011]meteors
2527:[Poi2011]MeteorsTimeLimit:60Sec MemoryLimit:128MBSubmit:1807 Solved:646[Submit][Status][Discuss]DescriptionByteotianInterstellarUnion(BIU)hasrecentlydiscoveredanewplanetinan 查看详情
bzoj2213[poi2011]differencedp
【BZOJ2213】[Poi2011]DifferenceDescriptionAwordconsistingoflower-caselettersoftheEnglishalphabet(‘a‘-‘z‘)isgiven.Wewouldliketochooseanon-emptycontiguous(i.e.one-piece)fragmentofthewordsoastomaximisethed 查看详情