64位Win8系统下安装Oracle12c

浏览数：17 / 时间：2015年06月12日

Count the string

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3658 Accepted Submission(s): 1696

Problem Description

It is well known that AekdyCoin is good at string problems as well as number theory problems. When given a string s, we can write down all the non-empty prefixes of this string. For example:
s: "abab"
The prefixes are: "a", "ab", "aba", "abab"
For each prefix, we can count the times it matches in s. So we can see that prefix "a" matches twice, "ab" matches twice too, "aba" matches once, and "abab" matches once. Now you are asked to calculate the sum of the match times for all the prefixes. For "abab", it is 2 + 2 + 1 + 1 = 6.
The answer may be very large, so output the answer mod 10007.

Input

The first line is a single integer T, indicating the number of test cases.
For each case, the first line is an integer n (1 <= n <= 200000), which is the length of string s. A line follows giving the string s. The characters in the strings are all lower-case letters.

Output

For each case, output only one number: the sum of the match times for all the prefixes of s mod 10007.

Sample Input

1
4
abab

Sample Output

Author

foreverlin@HNU

Source

HDOJ Monthly Contest – 2010.03.06

典型的kmp。。

只是超了两次时，

第一次是一个一个找，

如：aabcd 我找aa的时候就看bcd还有没有与它相匹配的，一次求出每个前缀匹配的次数。超时。。。。

第二次做了一下优化，

如：aabcd 我只找a，和aa匹配的个数，aab，aabc，aabcd都不找都为1个。超时。。。。。

第三次

如：abacd 我只要找到某个子串匹配的个数为1个，那么剩下的肯定也为一个。。。

我只要找第一个前缀a，他只有一个匹配的，后面的都不要找了。。

#include <cstdio>
#include <cstring>
char stu1[200001];
char stu2[200001];
int next[2000001];
int n;
int count;
void makeNext()
{
    int q,i;
    next[0]=0;
    for(i=1,q=0;i<n;++i)
    {
        while(q>0 && stu1[i]!=stu1[q])
        {
            q=next[q-1];
        }
        if(stu1[i]==stu1[q])
        {
            ++q;
        }
        next[i]=q;
    }
}
int kmp(int x)
{
    int sum=0;
    int q,i;
    for(i=x,q=0;i<n;++i)
    {
        while(q>0 && stu1[i]!=stu2[q])
        {
            q=next[q-1];
        }
        if(stu1[i]==stu2[q])
        {
            ++q;
        }
        if(q==x)
        {
            q=0;
            sum++;
        }
    }
    return sum;
}
int main()
{
    int t,i,k;
    while(~scanf("%d",&t))
    {
        while(t--)
        {
            scanf("%d",&n);
            getchar();
            scanf("%s",stu1);
            makeNext();
            stu2[0]=stu1[0];
            count=0;
            for(i=1;i<n;++i)
            {
                stu2[i]=stu1[i];
                k=kmp(i);
                if(k==0)
                    break;
                else
                    {
                        count+=k;
                        if(count>10007)
                           count%=10007;
                    }
            }
            count+=n;
            if(count>10007)
            count%=10007;
            printf("%d\n",count);
        }
    }
    return 0;
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

64位Win8系统下安装Oracle12c

标签： kmpkmp