Codeforces ZeptoLab Code Rush 2015 D.Om Nom and Necklace(kmp)

时间:2022-09-19 18:50:07

题目描述:

有一天,欧姆诺姆发现了一串长度为n的宝石串,上面有五颜六色的宝石。他决定摘取前面若干个宝石来做成一个漂亮的项链。

他对漂亮的项链是这样定义的,现在有一条项链S,当S=A+B+A+B+A+...+A+B+A的时候是漂亮的,这儿A,B是一些宝石串,“+”表示连接操作。S中有k+1个A和k个B组成。A和B可能是空串。

现在给出宝石串,问怎么切前几个才能得到一个漂亮的宝石项链。他切下来之后不会改变宝石的顺序。

样例解释:

在这个样例中前6个可以组成漂亮的串( A="", B="bca")。前7个也可以(A="b", B="ca")。

题解:

首先用kmp算法可以将字符串的一个前缀划分成SSSS....ST的形式。

下面考虑如果T=S,R为有多少个S,那么每个AB的要求就是要有R/k个S,最后会余下来R%k个S,那么把余下来的这部分当作A,其余部分当作B即可,这里B可以为空串

所以条件就是R/k-R%k>0

如果T!=S,每个AB的要求仍然是有R/k个S,最后会余下来R%k个S加上T,这时就需要把余下的部分当成A,剩下的部分当成B,但是这里B不能为空串,不然就不能凑出来AB(因为A不是S..SS,是S..ST)了

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn = 2e6;
int n, k;
char s[maxn];
int ans[maxn], fail[maxn];
int main()
{
cin>>n>>k;
cin>>s;
int j = ;
fail[] = ;
ans[] = ;
if(k == ) ans[] = ;
for(int i = ; i < n; i++){
j = fail[i];
while(j && s[i] != s[j]) j = fail[j];
j = s[i] == s[j] ? j+ : ;
fail[i+] = j; int Q = i-j+, R = (i+)/Q;
if((i+)%Q == ) ans[i] = R/k >= R%k;
else ans[i] = R/k > R%k;
}
for(int i = ; i < n; i++) putchar(ans[i] ? '' : '');
return ;
}