首页 > 代码库 > 模式匹配KMP算法

模式匹配KMP算法

前些日子在为目前该学习什么而苦恼,就问了一下已经从事多年软件开发的表哥,他说一个程序员要走的远,就要学好数据结构和算法,于是我就重新开始学习数据结构和算法了

拿起以前上过的数据结构看,看到第四章串的模式匹配时,颇感兴趣,就写了一下程序,实践了一下。感觉还蛮爽,于是就把以下几个重要的函数放在此处,以便后面查看和园友学习。

typedef char SString[MAX_STR_LEN + 1];//0号单元存放串的长度,可以存储的数字为-128----127

没有改进的模式匹配算法

int Index(SString S,SString T,int pos)

{

   int i=pos,j=1;

    while(i<=S[0]&&j<=T[0])

    {

       if(S[i]==T[j])

       {

         ++i;++j;//继续往后比较

      }

       else{i=i-j+2;j=1;}//指针后退重新匹配

   }

   if(j>T[0])

    {   return i-T[0];  }

   else return 0;

} //end of Index

//模式匹配算法KMP

//求模式串T的next函数值并存入数组next

void get_next(SString T,int next[])

{

    int i = 1,j = 0;  next[1] = 0;

    while (i < T[0])

    {

       if (j==0 || T[i]==T[j])   {    ++i;   ++j;    next[i] = j;   }

      else   {    j = next[j];   }

   }

}

 

//求模式串T的next函数修正值并存入数组nextval

void get_nextval(SString T,int nextval[])

{

    int i = 1,j = 0;  nextval[1] = 0;

      while (i < T[0])  

    {

         if (j==0 || T[i]==T[j])

        {

            ++i;   ++j;

                 if (T[i] != T[j])

             {     nextval[i] = j;    }

             else     {          nextval[i] = nextval[j];    }

        }

        else    {    j = nextval[j];   }

   }

}

 

//利用模式串T的next函数求T在主串S中第pos字符之后的位置的KMP算法//1=<pos=<StrLength(S)

int Index_KMP(SString S,SString T,int pos,int next[])

{

    int i = pos,j = 1;

    while (i<=S[0] && j<=T[0])

   {

       if (j==0 || S[i]==T[j])

       {   ++i;   ++j;  }

      else   {    j = next[j];   }  

   }

   if (j > T[0])

   {   return i - T[0];  }

   else  {   return 0;  }

}