[科技论文网] http://www.scipapers.com    2007-12-01  

朴素(Naive)字符串匹配算法

作者：hedongfu

 作为最原始的字符串匹配算法，它的时间复杂度是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;
}

    来源：

声明：本文由网友推荐或作者提交，版权归原作者所有，刊登此文仅为传播知识，展示研究成果，提高文章引用率。未经原作者授权，禁止用于任何形式的商业行为。科技论文网倡导尊重知识、尊重劳动、保护原创、知识共享。由于部分论文文章来于网络，文章作者不祥，请相关的原创作者与我们联系，以便加上您的署名。