2015年软考程序员算法实例：朴素字符串匹配算法
发布时间：2011/3/18 10:48:33 来源：城市学习网 编辑：ziteng
作为最原始的字符串匹配算法，它的时间复杂度是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
{
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
{
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;
}
