职业教育新东方网 > 职业教育 > 计算机 > 软件考试 > 初级资格 > 程序员 > 文章正文

2011年软考程序员算法实例:朴素字符串匹配算法

分享到:

2011-10-28 09:20  作者:  来源:互联网  字号:T|T

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

  {

  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< p>

  {

  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;

(责任编辑:单月)

 

热点课讯

精彩问答

提问