深入串的模式匹配算法(普通算法和KMP算法)的详解

//朴素的串的模式匹配算法，S为主串，T为模式串，即找S中有没有与T相同的字串
int Index(char *S, char *T, int pos)//pos记录从哪一位开始匹配可以直接用0代替
{
 int i=pos, j=0;
 while(i <strlen(S) && j <strlen(T))//确保未超出字符串的长度
 {
  if (S[i] == T[j])
      { ++i; ++j;} //如果相同，则继续向后比较
  else
      {i = i-j+1; j =0;} //如果不同，就回溯，重新查找
 }
 if (j == strlen(T))
  return i-strlen(T); //若匹配成功，返回S中与T字符串相同开始位置的索引
 else return 0; //若匹配不成功，返回0
}

void GetNext(char* T, int *next)
{
 int i=1,j=0;
 next[1]=0;
 while( i < strlen(T) )
 {
  if (j == 0 || T[i] == T[j])
  {
    ++i; ++j;
    next[i] = j;
  }
  else j = next[j];
 }
}
int KMP(char* S, char* T, int pos)
{
 int i = pos, j = 1;
 while (i)
 {
  if (S[i] == T[j])
  {
   ++ i;  ++ j;
  }
  else
   j = next[j];
 }
 if (j > strlen(T))
  return i-T[0];
 else
  return 0;
}

void GetNextEx(char *T, int *next)
{
 int i=1,j=0; next[1] = 0;
 while(i < strlen(T))
 {
  if (j == 0 || T[i] == T[j])
  {
   ++i; ++j;
   if (T[i] == T[j])
    next[i] = next[j];  //减少回退次数
   else   next[i] = j;  //和上面算法一样next[i]=j
  }
  else j = next[j];
 }
}