kmp算法--字符串比较

常规的比较算法（朴素比较算法）

int NaiveStringSearch(string S, string P)
{
    int i = 0;    // S 的下标
    int j = 0;    // P 的下标
    int s_len = S.size();
    int p_len = P.size();
    while (i < s_len && j < p_len)
    {
        if (S[i] == P[j])  // 若相等，都前进一步
        {
            i++;
            j++;
        }
        else               // 不相等
        {
            i = i - j + 1;
            j = 0;
        }
    }
    if (j == p_len)        // 匹配成功
        return i - j;
    return -1;
}

因为朴素算法效率低采用，KMP比较算法
比如说字符串，T=“abcdex”
j 123456
模式串 abcdex
next[j] 0111111
再比如说 T=“abcabx”
j 123456
模式串 abcabx
next[j] 011123

KMP模式匹配算法的实现

void get_next(String T,int *next)
{
   int i,j;
   i=1;
   j=0;
  next[1]=0;
while(i<T[0])//这里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;//i用于主串S当前位置的下表值，若pos不为1，则从pos位置开始匹配
int j=1;//用于子串T中当前位置的下标值，
int next[255];
get_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,即nextval数组值推导

void get_nextval(String T,int *nextval)
{
  int i,j;
  i=1;
  j=0;
 nextval[1]=0;
while(i<T[0])
{
   if(j==0||T[i]==T[j])
{
  ++i;
  ++j;
if(T[i]!=T[j])
  nextval[i]=j;
else
  nextval[i]=nextval[j];
}
else
     j=nextval[j];//若字符不同，则j值回溯
}
}

由于讲解太过于粗糙，仅供参考