| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 321 人关注过本帖
标题:超级病毒那个题加强版的,可惜没有用到指针
取消只看楼主 加入收藏
小赵q1
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:4
帖 子:492
专家分:777
注 册:2011-8-26
结帖率:100%
收藏
已结贴  问题点数:20 回复次数:1 
超级病毒那个题加强版的,可惜没有用到指针
仍然是超级病毒那个题目,计算小串在大串里面被包含了几次;
前几天写了个超级病毒那个题目的程序,大串和小串是一个字符一个字符的比较的,
例如:大串是:a[1000]="aaabbbaaabbbaaa",小串是:b[100]="bbbaaa";
如果从a[3]到a[8]都和小串相同,那么再开始从a[4]跟小串的第一个字符比较,朴素的模式匹配算法(思路简单,但不够简便,时间长,有回溯);
详情见:https://bbs.bccn.net/thread-363109-1-1.html
在网上看了kmp算法,有点看不懂,其实它的道理是很简单的,
   A.当字符串比较出现不等时,确定下一趟比较前,应该将大串 a 右移多少个字符;  
   B. 大串 a 右移后,应该从哪个字符开始和小串 b 中刚才比较时不等的那个字符继续开始比较。
仍然是没有看透,感觉被绕进去了,琢磨了好几天自己根据上面两个条件又写了个程序:
#include<stdio.h>
#include<string.h>
int main()
{
    char da[1000]="aaaaaattaa",xiao[100]="atta";
    int i,j,k=0,ci=0,xiaode,dade;
    xiaode=strlen(xiao);
    dade=strlen(da);
/*判断小串中有首尾有多少个字符是相同的,当大串和小串第一次相同时,大串的当前位置应该向左移动多少个字符。*/
    for(i=0;i<xiaode/2;)
    {
        if(xiao[i]==xiao[xiaode-1])
        {
            if(xiao[i+1]==xiao[i])
            {i++;xiaode--;}
            else i++;
        }
        else break;
    }
    xiaode=strlen(xiao);  //这里xiaode的值要重新判断一次,否则会因为上面的{i++;xiaode--;}而出错。
/*如果大串和小串的第一个字符不同,那么大串向右移动一个字符跟小串第一个字符比较,
  否则开始比较下一个字符,如果出现第一次相同,大串向左移动 i 个字符开始跟小串比较,*/
    for(j=0;j<dade;)
    {
        if(da[j]==xiao[k])
          {j++;k++;}
        else if(k>=xiaode)
        {j=j-i;k=0;ci++;}
        else k=0;
    }
    if(j>=dade&&k>=xiaode) //如果大串和小串的最后一个字符相同了,在上面ci不会+1,所以就写在这里了。
        ci=ci+1;
    printf("%d\n",ci);
    return 0;
}
可惜没有用到指针(改天再写个指针的,便于把指针理解的更透彻)
师傅写的程序运行很成功,但是如果当a[1000]="aaaaaaaaaaaaaabbaaaaaaaaaa",b[100]="abba"时,结果是错误的,
大家发表下建议,共同讨论下,呵呵,一起进步哦。
搜索更多相关主题的帖子: 字符串 网上 
2012-03-22 06:32
小赵q1
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:4
帖 子:492
专家分:777
注 册:2011-8-26
收藏
得分:0 
我用的是VC6.0,编译通过呀,你用的什么编译器?
2012-03-22 20:43
快速回复:超级病毒那个题加强版的,可惜没有用到指针
数据加载中...
 
   



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

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