作为最原始的字符串匹配算法，它的时间复杂度是O((n-m+1)m)
#include "stdio.h"
//计算字符串的长度
int Length(char *s)
{
int count=0;
while(*s++!='\0')
count++;
return count;
}
//字符串匹配
void NaiveStringMatching(char *t,char *p)
{
int n=Length(t);
int m=Length(p);
if(n<m)
{
printf("Error:The P is longer than T!\n");
return;
}
bool find=true;
printf("The string T is %s\n",t);
printf("The string P is %s\n",p);
for(int s=0;s<=n-m;s++)
{
find=true;
for(int i=0;i<m;i++)
{
if(t[s+i]!=p[i])
{
find=false;
break;
}
}
if(find)
printf("Pattern occurs with shift:%d\n",s+1);
}
}
int main()
{
char t[]="abcdebcg";
char p[]="bcdebcg";
NaiveStringMatching(t,p);
return 0;
}
发表评论 
打印本文
推荐本文
加入收藏
返回顶部
关闭窗口
