[HDU1358/UVA1328/SPOJ PERIDO/POJ1961/ZOJ2177]Period(KMP)

发布于 2018-02-20  159 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[HDU1358/UVA1328/SPOJ PERIDO/POJ1961/ZOJ2177]Period(KMP)

Description

For each prefix of a given string S with N characters (each character has an ASCII code between 97 and 126, inclusive), we want to know whether the prefix is a periodic string. That is, for each i (2 <= i <= N) we want to know the largest K > 1 (if there is one) such that the prefix of S with length i can be written as A K , that is A concatenated K times, for some string A. Of course, we also want to know the period K.

Http

HDU
UVA
SPOJ
POJ
ZOJ

Tag

KMP

题目大意

给出一个字符串,求所有能表示成若干循环串的前缀以及这些前缀的循环节个数。

解决思路

我们知道\(KMP\)算法求出的\(Next\)数组表示的是这个前缀的最长相同前缀后缀,那么,如果i是\(i-Next[i]\)的非\(1\)整数倍,就说明以\(i\)结尾的这个前缀是一个循环串,循环节长度为\(i-Next[i]\),循环节个数就为\(\frac{i}{i-Next[i]}\)。
为什么这样是对的呢?比如下面这个前缀
HDU-1358-1
根据\(Next[i]\)的定义,那么前面长度为\(L'\)的前缀\([1,L']\)一定与\([L'+1,2L']\)这一段相同,就是下面紫色和黄色的段。
HDU-1358-1
那么同理又有\([2L'+1,3L']\)相同,即下面黄色与橙色段。
HDU-1358-1
依次类推,可知如果\(L\)是\(L'\)的倍数,那么这个前缀就一定是循环的。

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[HDU1358/UVA1328/SPOJ PERIDO/POJ1961/ZOJ2177]Period(KMP)


HNCJ OIer