51nod 1554 KMP思维题

题目为中文，因而不再解释题意。

首先遵循如下设定可以有以下几个结论：
1，首先谈论下KMP的一个特殊性质：对于某一个特立独行的字符串：例如ABCDEF，在建立有限状态自动机之后，都会有，所有元素的失配边，指向0，也就是初始的那个元素。此时我们可以讲这个独立的元素及之前字符串理解为“ 一个循环次数为1的循环串 ”。对于其他情况，形如：ABCDEFGAB，可以将ABCDEFG理解为一个循环串，AB为下一个循环的两个多余元素，因此，我们可以把任意字符串看成“ 一个循环串+若干独立元素 ”的巧妙形式。

2，对于该形式，都可以发现，对于第K号元素最小循环节的尺寸应当为“ K-F[K] ”（随着规约不同增减1，此处采用刘汝佳蓝书中KMP的规约），那么，我们可以在这个基础上求出来“最小循环节”循环的次数——K/(K-F[K])。

3，应当认为，任意一个串，都构成（AB）*N+A的的形式。区别仅仅在于N的取值

4，应当认为，任何一个循环串，形如(A+B)*N，都自然的可以被认为是（A+B+A+B）*N+(A+B)*k的形式，即可以将若干个相同的循环节看成一个大的循环节。

5，前文中，我们知道了，“如何求出循环串的最小循环节”，以及“最小循环节的长度”，从而可以求出“最小循环节出现的次数”。则对于给定目标m来说，很容易求出，满足有且仅有M个大循环节时，每个大循环节的 “ 最小循环体数量 ”，同时，也可以求出来，在满足上述条件后，“ 剩余的循环体数量 ”容易理解，在任何情况下，剩余的循环体数量大于最小循环体数量则构成一个新的循环，意味着M+1明显不符合题设，应当直接排出。

回过头来发现刘汝佳蓝书第一道练习例题就讲的是这个233333333333

放AC代码如下：

#include<bits/stdc++.h>

using namespace std;

const long long MAXN=;

char tar[MAXN];

long long f[MAXN];

long long n,m;

void init()

{

    cin>>n>>m;

    cin>>tar;

    f[]=;f[]=;

    for(int i=;i<n;++i)

    {

        int j=f[i];

        while(j&&tar[i]!=tar[j])j=f[j];

        f[i+]= tar[i]==tar[j]? j+:;

    }

}

int main()

{

    cin.sync_with_stdio(false);

    init();

    for(int i=;i<=n;++i)

    {

        int val=i/(i-f[i]);

        if(i%(i-f[i]))

        {

            if(val/m>val%m)cout<<;

            else cout<<;

        }else

        {

            if(val/m>=val%m)cout<<;

            else cout<<;

        }

    }

    return ;

}

巴特西

51nod 1554 KMP思维题

最新文章

热门文章