刚看错题目了 只有一个病毒序列啊 那不用AC自动机

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

表示我也不会做 TL了- -  

本人是一只永远变不了菜鸟的小鸡

骄傲了吧？！ 少了一个蛋，

那题目描述太恶心了

题目说
第一行为病毒特征代码（长度不超过10000个字符）。

可是数组要开100000 才能过- - 我就在这纠结了很久 恶心的题目

题目的要求有：
1.时间限制：1000 ms  |  内存限制：65536 KB
2.第一行为病毒特征代码（长度不超过10000个字符）。第二行为待测DNA序列，此序列长度较长（长度不超过1000000个字符）。
时间内存都有限制，长度这么长，有难度！！！
要是没有时间内存的限制，应该没问题。

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

你不是写出来了吗，前面那个代码是对的啊
还有时间怎么看的啊

/66MS解法
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
 
char str[1000001];
char str1[20000];
int main(){
    int n,i,j,next[20000],len1,len2,cont;
    scanf("%d",&n);
    while(n--){
        scanf("%s",str1);
        scanf("%s",str);
    //kmp
        i=0;
        j=-1;
        len1=strlen(str1);
        len2=strlen(str);
        next[0]=-1;
        while(i<len1){
        if(j==-1 || str1[i]==str1[j]){
            ++i;
            ++j;
            next[i]=j;
        }else j=next[j];
    }
   
    i=0;
    j=0;
    cont=0;
    while(i<len2){
        if(j==-1 || str1[j]==str[i] ){
            ++i;
            ++j;
        }else j=next[j];
        if(j>=len1){
            cont++;
            i-=next[len1];//根据病毒串最后跟自己匹配的长度 主串后退相应的长度
            j=0;
        }
    }
    printf("%d\n",cont);
    }
return 0;
}

还有 为什么我上面的代码不能用 gun c提交啊郁闷- -
还有 老杨那代码 如果给组 病毒串长10000 主串长1000000的就超时了吧  时间复杂度要10000*999000吧

收到的鲜花

• laoyang103 于 2011-07-10 11:48 送鲜花  5朵   附言：我很赞同

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

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

我会再好好看看的