// KMP字符串模式匹配算法
// 輸入: S是主串,T是模式串,pos是S中的起始位置
// 輸出: 如果匹配成功返回起始位置,否則返回-1
int KMP(PString S, PString T, int pos)
{
    assert(NULL != S);
    assert(NULL != T);
    assert(pos >= 0);
    assert(pos < S->length);


if (S->length < T->length)
    return -1;

printf("主串\t = %s\n", S->str);
printf("模式串\t = %s\n", T->str);

int *next = (int *)malloc(T->length * sizeof(int));
// 得到模式串的next數組
GetNextArray(T, next);

int i, j;
for (i = pos, j = 0; i < S->length && j < T->length; )
{
    // i是主串游標,j是模式串游標
    if (-1 == j ||                // 模式串游標已經回退到第一個位置
        S->str[i] == T->str[j]) // 當前字符匹配成功
    {
        // 滿足以上兩種情況時兩個游標都要向前進一步
        ++i;
        ++j;
    }
    else                        //  匹配不成功,模式串游標回退到當前字符的next值
    {
        j = next[j];
    }
}

free(next);

if (j >= T->length)
{
    // 匹配成功
    return i - T->length;
}
else
{
    // 匹配不成功
    return -1;
}

}
//  得到字符串的next數組
 void  GetNextArray(PString pstr,  int  next[])
 {
    assert(NULL  !=  pstr);
    assert(NULL  !=  next);
    assert(pstr -> length  >   0 );

 //  第一個字符的next值是-1,因為C中的數組是從0開始的
 next[ 0 ]  =   - 1 ;
 for  ( int  i  =   0 , j  =   - 1 ; i  <  pstr -> length  -   1 ; )
 {
     //  i是主串的游標,j是模式串的游標
     //  這里的主串和模式串都是同一個字符串
      if  ( - 1   ==  j  ||                          //  如果模式串游標已經回退到第一個字符
         pstr -> str[i]  ==  pstr -> str[j])     //  如果匹配成功
      {
         //  兩個游標都向前走一步
          ++ i;
         ++ j;
         //  存放當前的next值為此時模式串的游標值
         next[i]  =  j;
    }
     else                                  //  匹配不成功j就回退到上一個next值
      {
        j  =  next[j];
    }
}

}
include  < stdio.h >
include  < stdlib.h >
include  < assert.h >
include  < string .h >
define  MAX_LEN_OF_STR    30             //  字符串的最大長度
typedef  struct  String                 //  這里需要的字符串數組,存放字符串及其長度
 {
     char     str[MAX_LEN_OF_STR];     //  字符數組
      int         length;                     //  字符串的實際長度
 } String,  * PString;
//  得到字符串的next數組
 void  GetNextArray(PString pstr,  int  next[])
 {
    assert(NULL  !=  pstr);
    assert(NULL  !=  next);
    assert(pstr -> length  >   0 );

 //  第一個字符的next值是-1,因為C中的數組是從0開始的
 next[ 0 ]  =   - 1 ;
 for  ( int  i  =   0 , j  =   - 1 ; i  <  pstr -> length  -   1 ; )
 {
     //  i是主串的游標,j是模式串的游標
     //  這里的主串和模式串都是同一個字符串
      if  ( - 1   ==  j  ||                          //  如果模式串游標已經回退到第一個字符
         pstr -> str[i]  ==  pstr -> str[j])     //  如果匹配成功
      {
         //  兩個游標都向前走一步
          ++ i;
         ++ j;
         //  存放當前的next值為此時模式串的游標值
         next[i]  =  j;
    }
     else                                  //  匹配不成功j就回退到上一個next值
      {
        j  =  next[j];
    }
}

}
//  KMP字符串模式匹配算法
 //  輸入: S是主串,T是模式串,pos是S中的起始位置
 //  輸出: 如果匹配成功返回起始位置,否則返回-1
 int  KMP(PString S, PString T,  int  pos)
 {
    assert(NULL  !=  S);
    assert(NULL  !=  T);
    assert(pos  >=   0 );
    assert(pos  <  S -> length);

 if  (S -> length  <  T -> length)
     return   - 1 ;

printf( " 主串\t = %s\n " , S -> str);
printf( " 模式串\t = %s\n " , T -> str);

 int   * next  =  ( int   * )malloc(T -> length  *   sizeof ( int ));
 //  得到模式串的next數組
 GetNextArray(T, next);

 int  i, j;
 for  (i  =  pos, j  =   0 ; i  <  S -> length  &&  j  <  T -> length; )
 {
     //  i是主串游標,j是模式串游標
      if  ( - 1   ==  j  ||                  //  模式串游標已經回退到第一個位置
         S -> str[i]  ==  T -> str[j])  //  當前字符匹配成功
      {
         //  滿足以上兩種情況時兩個游標都要向前進一步
          ++ i;
         ++ j;
    }
     else                          //   匹配不成功,模式串游標回退到當前字符的next值
      {
        j  =  next[j];
    }
}

free(next);

 if  (j  >=  T -> length)
 {
     //  匹配成功
      return  i  -  T -> length;
}
 else
  {
     //  匹配不成功
      return   - 1 ;
}

}/這就是最后的程序了
/</pre>