超级病毒
时间限制：1000 ms  |  内存限制：65536 KB
描述
在ACM训练基地最引人注目的一台计算机是一台具有高度人工智能的超级生物计算机。和其他所有计算机不同，这台计算机拥有和人类一样的DNA结构。由于具有高度的人工智能，各位训练队员们都早已把它当成是训练队里不可缺少的一员。


有一天，它们发现这台计算机生病了……


生病以后，这台计算机变得很虚弱，不和我们打招呼了，也不能帮我们想算法题了。队员们都很难过，他们都想帮帮这位好朋友。


经过仔细的检查，它们发现这台计算机感染了一种病毒。和医学中的病毒一样，这种超级病毒侵入计算机运算单元内的细胞，将其感染。于是，正常细胞中的DNA被病毒更改为新的序列。导致细胞机能的变异。


经过仔细比对，训练队员们已经找到了可疑的病毒特征序列，即，如果细胞的DNA序列中包含这种序列，那么该细胞就很可能被感染。


例如，病毒特征代码为ATAA，则如果DNA序列中如果有ATCATAATCATAC这样一段，则细胞就很可能受到感染。


现在，队员们将为生病计算机进行彻底的检查，他们将给出计算机完整的DNA序列（和生物学中的DNA一样，计算机的DNA序列也可以表示为字母A,T,C,G组成的序列），你的任务是，判定该DNA序列中出现过几次病毒特征序列。


注意：其中病毒特征序列在待测DNA序列中重叠出现必须按多次计算。


例如： AATTAATTAA在AATTAATTAATTAA中出现两次。

输入
输入包括多组测试数据，第一行有一个正整数N表示数据数量。
以下为N组测试数据。
每组测试数据由两行，每一行都是由字母A、T、C、G组成的字符串。第一行为病毒特征代码（长度不超过10000个字符）。第二行为待测DNA序列，此序列长度较长（长度不超过1000000个字符）。


输出
对于每一组测试数据，输出一个整数表示答案，为在待测DNA序列中出现病毒特征代码的次数。

样例输入
1
AATTAATTAA
AATTAATTAATTAA
样例输出
2

代码写好的 自己去测试 http://www.
过的发消息  老杨谢过

你去试试就知道了  数据量太大

想出来啦  谢谢大家了  其实就是最多有 主串长度-字串长度+1个匹配

这样肯定不会超时  不过还是100ms 可见数据量之大

#include<stdio.h>
#include<string.h>
char a[1000001] = {0};
char b[10001] = {0};
int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        int sum = 0;
        scanf("%s",b);
        scanf("%s",a);
        int len = strlen(b);
        int slen = strlen(a);
        int cool = slen-len+1;
        int i = 0;
        while(cool--)
        {
            char *p = b;
            char *q = a+i;
            while(*p)
            {
                if(*p == *q)
                {p++;q++;}
                else
                    break;
            }
            if(!*p)
                sum++;
            i++;
        }
        printf("%d\n",sum);
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
    }
    return 0;       
}

[ 本帖最后由 laoyang103 于 2011-7-9 19:01 编辑 ]

#include<time.h>
#include <iostream.h>
int main()
{
clock_t start,finish;
start=clock();
for(int i = 0;i<1000000;i++);
finish=clock();
cout<< (double)(finish - start)<<"ms";//运行时间:
return 0;
}

但是我没有测试数据  运行时间是OJ上写的  一半不着急计算时间

因为你不可能写1000000的测试数据

本人菜鸟   这道题做了一下午  惭愧  

对于这种题暴力求解一定超时   

恩  效率确实能不相比  楼上的代码相当牛  老杨学习了

谢过  一直以为KMP只能做匹配 没想到可以这样用 看来我对KMP还是理解的不深

我会再好好看看的