KMP模式匹配算法实现与改进

/*KMP模式匹配算法实现*/  //通过计算返回子串T的next数组  void get_next(String T,int * next)  {   int i,j;   i = 1;   j = 0;   next[1] = 0;   while (i < T[o]) //T[0]表示串T的长度   {    if (j == 0 || T[i] == T[j]) //T[i]表后缀的单个字符，T[j]表前缀的单个字符    {     ++i;     ++j;     next[i] = j;    }    else     j = next[j]; //若字符不相同，则j值回溯   }  }    //返回子串T在主串S中的pos个字符之后的位置。若不存在返回值0  int Index_KMP(String S,String T,int pos)  {   int i = pos;   int j = 1;   int next[255]; //定义一个next数组   get_next(T,next); //对串T作分析，得到next数组   while (i <= S[0] && j<= T[0]) //S[0]和T[0]为主串个子串的长度   {    if (j == 0 || S[i] == T[j])    {     ++i;     ++j;       }    else    {     j = next[j]; //j退回合适的位置，i值不变    }   }   if (j > T[0])    return i-T[0];   else    return 0;  }

/*KMP模式匹配算法的改进*/  //通过计算返回子串T的nextval数组  void get_nextval(String T,int * nextval)  {   int i,j;   i = 1;   j = 0;   nextval[1] = 0;   while (i < T[0]) //T[0]表示串T的长度   {    if (j == 0 || T[i] == T[j]) //T[i]表后缀的单个字符，T[j]表前缀的单个字符    {     ++i;     ++j;     if (T[i] != T[j]) //若当前字符与前缀字符不同      nextval[i] = j; //则当前的j为nextval在i位置的值     else      nextval[i] = nextval[j]; //如果字符相同，则将前缀字符的nextval值赋给nextval在i位置的值    }    else     j = nextval[j]; //若字符不相同，则j值回溯   }  }