标签：子串 主串 ch nextval ++ next 算法 KMP

1-从oneNote上搬来

2-代码

String数据结构

//串的堆分配存储结构（malloc占用的是堆空间）
struct HString
{
    char *ch;   //若是非空串，则按串长分配存储区；否则ch为NULL
    int length; //串长度
};
typedef HString String;

2.1 计算next数组（下标从1开始）

//计算next数组
void get_next(String T, int next[])
{
    int i = 1, j = 0;
    next[1] = 0;
    while (i < T.length) // i遍历串中的每个字符（主串）
    {
        if (j == 0 || T.ch[i] == T.ch[j]) //子串第一个元素失配||主串与子串指针处字符相同
        {
            ++i;
            ++j;
            next[i] = j;
            // 1 子串第一个元素失配：主串下标为i的元素next值为1(next[i]=1)
            // 1 第二次进while若还是子串第一个元素失配，则j=next[1]=0
            // 1 第三次进while时执行与第一次进while时相同的操作：next[i]=1
            // 2 主串i与子串j处字符相同：主串下标为i的元素next值为j+1
        }
        else //主串i与子串j处字符失配，且j不为0（j为1时来过渡一下）
            j = next[j];
    }
}

2.2 计算next数组（下标从0开始）

//计算next数组,下标0开始
void get_next_0(String T, int next[])
{
    int i = 0, j = -1;
    next[0] = -1;
    while (i < T.length)
    {
        if (j == -1 || T.ch[i] == T.ch[j])
            next[++i] = ++j;
        else
            j = next[j];
    }
}

2.3 计算nextval数组（求next数组优化版）

//计算next数组-优化
void get_nextval(String T, int nextval[])
{
    int i = 1, j = 0;
    nextval[1] = 0;
    while (i < T.length) // i遍历串中的每个字符（主串）
    {
        if (j == 0 || T.ch[i] == T.ch[j]) //子串第一个元素失配||主串与子串指针处字符相同
        {
            ++i;
            ++j;
            if (T.ch[i] != T.ch[j]) // i++，j++后，串与子串指针处字符不相同
                nextval[i] = j;
            else //主串与子串有连续两个字符相等
                nextval[i] = nextval[j];
                }
        else //主串i与子串j处字符失配，且j不为0（j为1时来过渡一下）
            j = nextval[j];
    }
}

 

标签：子串,主串,ch,nextval,++,next,算法,KMP
From： https://www.cnblogs.com/FishSmallWorld/p/17084094.html