KMP算法代码实现

先上代码

int  getNextArray(char a[], int n, int *p)
{
   if(NULL == a || 0 == n)
   {
      return -1;
   }

   p[0] = -1;
   p[1] = 0;
   int pos = 2;
   int ch = 0;

   while(pos < n)
   {
     if(a[pos] == a[ch])
     {
         p[pos] = p[pos - 1] + 1;
         pos ++;
         ch ++;

     }
     else if(0 != ch)
     {
       ch = p[ch];
     }
     else
     {
       p[pos] = 0;
       pos ++;
     }

   }

   return 0;

}

int matchIndex(char dest[],int destLen, char match[], int matchLen)
{
   if(NULL == dest || NULL == match || destLen < matchLen)
   {
     return -1;
   }

   int nextArray[N]={0};
   int nError = getNextArray(match,  matchLen, nextArray);
   if(0 != nError)
   {
     return -1;
   }

   int dIndex = 0;
   int mIndex = 0;
   while(dIndex < destLen && mIndex < matchLen)
   {
     if(dest[dIndex] == match[mIndex])
     {
        dIndex ++ ;
        mIndex++;
     }
     else
     {

        if(mIndex < 2)
        {
            dIndex ++;
            mIndex = 0;
        }
        else
        {
            mIndex = nextArray[mIndex-1] ;
        }
     }

    }

   if(mIndex == matchLen)
   {
      return dIndex - matchLen + 1;
   }
   else
   {
      return -2;
   }
}