超级病毒那个题加强版的,可惜没有用到指针
仍然是超级病毒那个题目,计算小串在大串里面被包含了几次;前几天写了个超级病毒那个题目的程序,大串和小串是一个字符一个字符的比较的,
例如:大串是: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"时,结果是错误的,
大家发表下建议,共同讨论下,呵呵,一起进步哦。