3.3知识精炼（二）高清版本.pdf

知识精炼（二）

主讲人：邓哲也

Codeforces526DOnNomandNecklace

给出一个字符串s，判断其每个前缀是否可以表示成

ABAB…ABA的形式（A和B都可以为空，但是必须满足A

有k+1个，B有k个）

|s|,k≤106

长度为6的前缀，可以取A=“”,B=“bca”

长度为7的前缀，可以取A=“b”,B=“ca”

Codeforces526DOnNomandNecklace

对于前缀P，我们可以把P拆成SSSS…ST，其中T是S

的前缀。

这样就可以用KMP来做了。

首先i-next[i]就是S[1..i]这一段的最小循环节的长度，

记为e。

可以发现e的倍数je也是循环节。

Codeforces526DOnNomandNecklace

什么情况下存在划分方案呢？

i/(je)=k或(je)|i且i/(je)=k+1

这样就可以求出是否存在j了。

时间复杂度O(n)

Codeforces526DOnNomandNecklace

intcheck(inti,inte){

intup=i/k/e;

intdn=ceil((l/(k+1)+1)/float(e));

returnup=dn

||

(i%(k+1)==0(i/(k+1))%e==

0;

}

下节课再见