Android - 按钮组件详解

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
6
 

Author
foreverlin@HNU
 

Source



典型的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;
}


Android - 按钮组件详解

上一篇:手机浏览器添加到主屏幕(桌面)的图标设置以及WebApp模式


下一篇:Android通讯录开发之实现全选、反选功能