51nod 1554：欧姆诺姆和项链—

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1554

题目：

有一天，欧姆诺姆发现了一串长度为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"）。

Input

单组测试数据。

第一行有两个整数n, k (1≤n,k≤1 000 000)，表示宝石串原始的长度和在上文中提到的参数k。

第二行有n个由小写字母组成的串，表示原始宝石串。

Output

输出一行有n个01组成的字符串。第i(1≤i≤n)个位置是1的时候表示前i个宝石可以组成漂亮的宝石项链。

Input示例

样例输入1

7 2

bcabcab

Output示例

样例输出1

0000011

那么，很显然这是KMP比较难的题。

（因为我最开始想了暴力，然而看了数据范围emmmmmm……）

这里我们可以将原串分为两种串S与T。

那么可能会将其分为SSS……SSS或SSS……SSST

对于第一种情况，显然我们可求S的个数num（num=n/(n-nxt[n])）（请见上篇文章）

那么num/k就是ABAB……BABA中AB所包含的S的个数，自然的num%k就是A所包含的S的个数。

由于B可空，所以num/k>=num%k。

对于第二种情况，思考一下发现num的求法同上。

那么我们将A=T，B=（S-T）+SSS……SSS。

AB的S个数仍然是num/k，T的S个数仍然是num%k。

但是T！=S，所以num/k>num%k

（PS.本题输出量巨大，请使用快速的输出方式）

#include<cstdio>

#include<cstring>

using namespace std;

const int N=1e6+;

char s[N];

int nxt[N];

char ans[N];

void getnext(int m){

    int j=;

    for(int i=;i<=m;i++){

        while(j!=&&s[j+]!=s[i])j=nxt[j];

        if(s[j+]==s[i])j++;

        nxt[i]=j;

    }

    return;

}

int main(){

    int m,k;

    scanf("%d%d%s",&m,&k,s+);

    memset(ans,'',sizeof(ans));

    getnext(m);

    for(int n=;n<=m;n++){

    int num=n/(n-nxt[n]);

    if(n%(n-nxt[n])==){

        if(num/k>=num%k){

        ans[n-]='';

        }

    }else{

        if(num/k>num%k){

        ans[n-]='';

        continue;

        }

    }

    }

    ans[m]=;

    puts(ans);

    return ;

}

巴特西

51nod 1554：欧姆诺姆和项链——题解

最新文章

热门文章