HDU Count the string+Next数组测试函数

时间：2022-05-07 22:36:24

链接：http://www.cnblogs.com/jackge/archive/2013/04/20/3032942.html

题意：给定一字符串，求它所有的前缀出现的次数的和。
这题很纠结，一开始不知道怎么做，如果直接统计子串在主串中出现的次数，orz···肯定
TLE，后来发现这题可以直接从next数组入手，因为next数组表示的是子串中最长公共前后缀串的长度，如果用dp[i]表示该字符串前i个字符中出
现任意以第i个字符结尾的前缀的次数，它的递推式是
dp[i]=dp[next[i]]+1,即以第i个字符结尾的前缀数等于以第next[i]个字符为结尾的前缀数加上它自己本身，这里要好好理解一下，不
太好解释。
举个例子：
              i  1 2 3 4 5 6
        字符串  a b a b a b
        dt[i]  1 1 2 2 3 3
        aba中出现的前缀为a,aba,所以dt[3]是2，ababa中出现的前缀为a,aba,ababa,所以dp[5]是3，当i=5时,next[5]=3，所以dp[i]=dp[next[i]]+1
理解了上面的部分就很简单了，后面直接套next数组的模板

第二次理解：

　　弄出next数组，之后其中的值就是要跳回去的位置，比如 ababab 0 0 1 2 3 4 当i=1，就跳到0的位置加一个，i=2，跳到0的位置加一个，i=3跳到1的位置加一个，（并且1的位置已经有一个了）所以就是2，以此类推……

#include <bits/stdc++.h>

using namespace std;

const int INF=0x3f3f3f3f;

typedef long long LL;

#define PI(A) printf("%d\n",A)

#define SI(N) scanf("%d",&(N))

#define SII(N,M) scanf("%d%d",&(N),&(M))

#define cle(a,val) memset(a,(val),sizeof(a))

#define rep(i,b) for(int i=0;i<(b);i++)

#define Rep(i,a,b) for(int i=(a);i<=(b);i++)

#define reRep(i,a,b) for(int i=(a);i>=(b);i--)

const double EPS= 1e- ;

/*  /////////////////////////     C o d i n g  S p a c e     /////////////////////////  */

const int MAXN=  +  ;

//kuangbin 模板

void kmp_pre(char x[],int m,int Next[])

{

    int i,j;

    j=Next[]=-;

    i=;

    while(i<m)

    {

        while(-!=j&&x[i]!=x[j]) j=Next[j];

        Next[++i]=++j;

    }

}

char str[MAXN];

int Next[MAXN];

int dp[MAXN];

int M=;

int main()

{

    int o;

    SI(o);

    while(o--)

    {

        int n;

        SI(n);

        scanf("%s",str);

        kmp_pre(str,n,Next);

        int ans=;

        Rep(i,,n)

        {

            dp[i]=dp[Next[i]]+;

            ans=(ans+dp[i])%M;

        }

        PI(ans);

    }

    return ;

}

以下是next测试函数，可以自己测一下，有助于理解next原理

随便输入字符串，最后输出字符串，和对应next的值，

#include <bits/stdc++.h>

using namespace std;

const int INF=0x3f3f3f3f;

typedef long long LL;

#define PI(A) printf("%d\n",A)

#define SI(N) scanf("%d",&(N))

#define SII(N,M) scanf("%d%d",&(N),&(M))

#define cle(a,val) memset(a,(val),sizeof(a))

#define rep(i,b) for(int i=0;i<(b);i++)

#define Rep(i,a,b) for(int i=(a);i<=(b);i++)

#define reRep(i,a,b) for(int i=(a);i>=(b);i--)

const double EPS= 1e- ;

/*  /////////////////////////     C o d i n g  S p a c e     /////////////////////////  */

const int MAXN=  +  ;

//kuangbin 模板

void kmp_pre(char x[],int m,int Next[])

{

    int i,j;

    j=Next[]=-;

    i=;

    while(i<m)

    {

        while(-!=j&&x[i]!=x[j]) j=Next[j];

        Next[++i]=++j;

    }

}

char str[MAXN];

int Next[MAXN];

int dp[MAXN];

int M=;

int main()

{

    while(~scanf("%s",str))

    {

        kmp_pre(str,strlen(str),Next);

        printf("   ");

        rep(i,strlen(str))

        {

            printf("%c ",str[i]);

        }puts("");

        rep(i,strlen(str)+)

        {

            printf("%d ",Next[i]);

        }puts("");

    }

    return ;

}

引用大牛的话：

　　个人认为，next数组在求解的过程中，用到了KMP的思想，当前失配了，就回溯到上一个next，请见 j=next[j] ，先说个结论，如果到位置 i ，如果有

i%(i-next(i))==0 , 那说明字符串开始循环了，并且循环到 i-1 结束，为什么这样呢？

　　我们先假设到达位置 i-1 的时候，字符串循环了（到i-1完毕），那么如果到第i个字符的时候，失配了，根据next数组的求法，我们是不是得回溯？

然而回溯的话，由于字符串是循环的了（这个是假定的），next[i] 是不是指向上一个循环节的后面一个字符呢？？

是的，上一个循环节的末尾是 next[i]-1 ，然后现在循环节的末尾是 i-1 ，然么循环节的长度是多少呢？

所以，我们有 (i - 1) - ( next[i] - 1 ) = i - next[i]  就是循环节的长度（假设循环成立的条件下），但是我们怎么知道这个循环到底成立吗？

　　现在我们已经假设了 0 — i-1 循环了，那么我们就一共有 i 个字符了，如果有 i % ( i - next[i] ) == 0，总的字符数刚好是循环节的倍数，那么说明这个循环是成立的。

注意还有一点，如果 next[i] == 0，即使符合上述等式，这也不是循环的，举个反例

0   1    2   3   4   5

a    b   c   a   b   d

-1   0   0   0   1   2

下标为1,2,3的next值均为0，那么 i%（i-next[i]）=i%i==0，但是这个并不是循环。

解释完毕，然后再来看下，为什么求出来的循环节长度是最小的呢？

因为next数组失配的时候，总是回溯到最近的循环节，所以i-next[i]就是最小的循环节长度

为什么求出来的循环次数是最多的呢？

循环节长度是最小的了，那么循环次数肯定是最多的了。

总结一下：

如果对于next数组中的 i， 符合 i % ( i - next[i] ) == 0 && next[i] != 0 ,则说明字符串循环，而且

循环节长度为:  i - next[i]  （因为i - next[i]比较小）

循环次数为:  i / ( i - next[i] )  （因为总长是i，每节长i - next[i]，所以次数就是i / ( i - next[i] )）

相关文章