//樸素的串的模式匹配算法，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;} //如果相同，則繼續(xù)向后比較
  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];  //減少回退次數(shù)
   else   next[i] = j;  //和上面算法一樣next[i]=j
  }
  else j = next[j];
 }
}