| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1181 人关注过本帖
标题:谁帮帮我 实在做不出来了
只看楼主 加入收藏
laoyang103
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:内蒙古包头
等 级:贵宾
威 望:19
帖 子:3082
专家分:11056
注 册:2010-5-22
结帖率:95.24%
收藏
已结贴  问题点数:20 回复次数:20 
谁帮帮我 实在做不出来了
超级病毒
时间限制: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.
过的发消息  老杨谢过
搜索更多相关主题的帖子: 人工智能 计算机 超级病毒 好朋友 时间 
2011-07-09 18:18
hjywyj
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:3
帖 子:1114
专家分:2611
注 册:2010-4-14
收藏
得分:0 
这种小题应该难不倒你啊?
2011-07-09 18:20
laoyang103
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:内蒙古包头
等 级:贵宾
威 望:19
帖 子:3082
专家分:11056
注 册:2010-5-22
收藏
得分:0 
你去试试就知道了  数据量太大

                                         
===========深入<----------------->浅出============
2011-07-09 18:24
多布斯的喵喵
Rank: 2
等 级:论坛游民
帖 子:133
专家分:24
注 册:2011-3-29
收藏
得分:0 
俺是来占座滴啥也不懂
2011-07-09 18:32
laoyang103
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:内蒙古包头
等 级:贵宾
威 望:19
帖 子:3082
专家分:11056
注 册:2010-5-22
收藏
得分:0 
想出来啦  谢谢大家了  其实就是最多有 主串长度-字串长度+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 编辑 ]

                                         
===========深入<----------------->浅出============
2011-07-09 18:55
hjywyj
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:3
帖 子:1114
专家分:2611
注 册:2010-4-14
收藏
得分:0 
回复 5楼 laoyang103
怎样计算用了多长时间呢?
2011-07-09 18:57
laoyang103
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:内蒙古包头
等 级:贵宾
威 望:19
帖 子:3082
专家分:11056
注 册:2010-5-22
收藏
得分:0 
程序代码:
#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的测试数据

                                         
===========深入<----------------->浅出============
2011-07-09 19:06
ouyangouyang
Rank: 7Rank: 7Rank: 7
等 级:黑侠
帖 子:273
专家分:579
注 册:2009-10-8
收藏
得分:0 
图片附件: 游客没有浏览图片的权限,请 登录注册

后面那个函数是什么意思,解释一下,大牛哥

多少恨, 昨夜梦魂中。 还似旧时游上苑, 车如流水马如龙; 花月正春风!
2011-07-09 21:48
lz1091914999
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:四川
等 级:贵宾
威 望:37
帖 子:2011
专家分:5959
注 册:2010-11-1
收藏
得分:10 
晕,你不是已经过OJ了吗?还要追求Perfect?

My life is brilliant
2011-07-09 22:03
草狼
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:2
帖 子:577
专家分:1040
注 册:2010-4-6
收藏
得分:10 
这题是AC自动机的入门题目 老杨去看看AC自动机哈
2011-07-09 22:35
快速回复:谁帮帮我 实在做不出来了
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.065668 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved