当前位置: 首页 > 工具软件 > Next > 使用案例 >

求next数组详解

翁宏茂
2023-12-01

前缀、后缀、部分匹配值

"前缀"指除了最后一个字符以外,字符串的所有头部组合;
"后缀"指除了第一个字符以外,字符串的所有尾部组合。
“部分匹配值”是"前缀"和"后缀"的最长的共有元素的长度

以"abcdabd"为例

- "a"的前缀和后缀都为空集,共有元素的长度为0;

- "ab"的前缀为[a],后缀为[b],共有元素的长度为0;

- "abc"的前缀为[a, ab],后缀为[bc, c],共有元素的长度0;

- "abcd"的前缀为[a, ab, abc],后缀为[bcd, cd, d],共有元素的长度为0;

- “abcda"的前缀为[a, ab, abc, abcd],后缀为[bcda, cda, da, a],共有元素为"a”,长度为1;

- “abcdab"的前缀为[a, ab, abc, abcd, abcda],后缀为[bcdab, cdab, dab, ab, b],共有元素为"ab”,长度为2;

- "abcdabd"的前缀为[a, ab, abc, abcd, abcda,abcdab],后缀为[bcdabd, cdabd, dabd, abd, bd,d],共有元素的长度为0。

部分匹配(Partial Match,PM)表

下标01234567891011
模式串 Tababaaababaa
PM值001231123456

next数组求解方法

已知串T=“ababaaababaa”;

一、模式串的下标从0开始,此种方式的next数组求解方式:

此种方式的next数组就是上述PM值右移一位,空出的下标为0的位置赋值为-1(此处的-1是为了方便判断,也可以是其他值,自己斟酌即可)

下面从代码的角度讲述一下求解next[]的思路:

1、首先可以确定  next[0] = -1;  next[1] = 0; 后面求解每一位的next值时,根据前一位进行比较。
2、从第三位开始,也就是从T[2]开始,比较前一位元素与其next值对应的元素是否相同
3、若相同,则所求next值就等于前一位元素对应的next值 +1
4、若不同,则向前继续寻找next值对应的元素与前一位进行比较,直到找到与前一位元素相同的元素,
   若找到,则找到的这个位置的next值+1 就是我们所求的next值
5、若直到第一个元素,都没有找到与前一位元素相同的元素,则所求next值为0

1、可以确定前两位的值:next[0] = -1 ,next[1] = 0;

下标01234567891011
模式串 Tababaaababaa
next[ ]-10

2、看第三位,也就是T[2],看T[2]的前一位T[1]对应元素是b,T[1]所对应的next值是0,0对应的元素是a,b与a不同,继续向前寻找next值,也就是找T[0]的next值为-1,表示T[1]之前没有找到与自身相等的元素,则第三位T[2]=a的next值为0,也就是next[2]=0

下标01234567891011
模式串 Tababaaababaa
next[ ]-100

3、看第四位,也就是T[3],看T[3]的前一位T[2]对应元素是a,T[2]所对应的next值是0,0对应的元素是a,a与a相同,则T[3]对应的next值就是T[2]的next值+1 ,next[3] = 1;

下标01234567891011
模式串 Tababaaababaa
next[ ]-1001

4、看第五位,也就是T[4],看T[4]的前一位T[3]对应元素是b,T[3]所对应的next值是1,1对应的元素是b,b与b相同,则T[4]对应的next值就是T[3]的next值+1 ,next[4] = 2;

下标01234567891011
模式串 Tababaaababaa
next[ ]-10012

5、看第六位,也就是T[5],看T[5]的前一位T[4]对应元素是a,T[4]所对应的next值是2,2对应的元素是a,a与a相同,则T[5]对应的next值就是T[4]的next值+1 ,next[5] = 3;

下标01234567891011
模式串 Tababaaababaa
next[ ]-100123

6、看第七位,也就是T[6],看T[6]的前一位T[5]对应元素是a,T[5]所对应的next值是3,3对应的元素是b,a与b不同,则向前继续寻找next值,找到T[3]对应的next值是1,1对应的元素是b,a与b不同,继续向前寻找next值,T[1]对应的next值是0,0对应的元素是a,a与a相同,则T[6]对应的next值就是T[1]的 next值 +1,next[6] = 1;

下标01234567891011
模式串 Tababaaababaa
next[ ]-1001231

7、看第八位,也就是T[7],看T[7]的前一位T[6]对应元素是a,T[6]所对应的next值是1,1对应的元素是b,a与b不同,则向前继续寻找next值,T[1]对应的next值是0,0对应的元素是a,a与a相同,则T[7]对应的next值就是T[1]的 next值 +1,next[7] = 1;

下标01234567891011
模式串 Tababaaababaa
next[ ]-10012311

8、看第九位,也就是T[8],看T[8]的前一位T[7]对应元素是b,T[7]所对应的next值是1,1对应的元素是b,b与b相同,则T[8]对应的next值就是T[7]的 next值 +1,next[8] = 2;

下标01234567891011
模式串 Tababaaababaa
next[ ]-100123112

9、看第十位,也就是T[9],看T[9]的前一位T[8]对应元素是a,T[8]所对应的next值是2,2对应的元素是a,a与a相同,则T[9]对应的next值就是T[8]的 next值 +1,next[9] = 3;

下标01234567891011
模式串 Tababaaababaa
next[ ]-1001231123

10、看第十一位,也就是T[10],看T[10]的前一位T[9]对应元素是b,T[9]所对应的next值是3,3对应的元素是b,b与b相同,则T[10]对应的next值就是T[9]的 next值 +1,next[10] = 4;

下标01234567891011
模式串 Tababaaababaa
next[ ]-10012311234

11、看第十二位,也就是T[11],看T[11]的前一位T[10]对应元素是a,T[10]所对应的next值是4,4对应的元素是a,a与a相同,则T[11]对应的next值就是T[10]的 next值 +1,next[11] = 5;

下标01234567891011
模式串 Tababaaababaa
next[ ]-100123112345

二、模式串下标从1开始,此种方式的next数组求解方式

此种方式的next数组就是上述PM值右移一位,空出的下标为0的位置赋值为-1,然后所有值整体+1得到next数组

下面从代码的角度讲述一下求解next[]的思路:

1、首先可以确定  next[1] = 0;  next[2] = 1 ; 后面求解每一位的next值时,根据前一位进行比较。 
2、从第三位开始,也就是从T[3]开始,比较前一位元素与其next值对应的元素是否相同
3、若相同,则所求next值就等于前一位元素对应的next值 +1
4、若不同,则向前继续寻找next值对应的元素与前一位进行比较,直到找到与前一位元素相同的元素,
   若找到,则找到的这个位置的next值+1 就是我们所求的next值
5、若直到第一个元素,都没有找到与前一位元素相同的元素,则所求next值为1

1、可以确定前两位的值:next[1] = 0 ,next[2] = 1;

下标123456789101112
模式串 Tababaaababaa
next[ ]01

2、看第三位,也就是T[3],看T[3]的前一位T[2]对应元素是b,T[2]所对应的next值是1,1对应的元素是a,b与a不同,继续向前寻找next值,也就是找T[1]的next值为0,0没有对应的元素,表示没有找到与T[2]也就是b相等的元素,则第三位T[3]的next值为1,也就是next[3]=1

下标123456789101112
模式串 Tababaaababaa
next[ ]011

3、看第四位,也就是T[4],看T[4]的前一位T[3]对应元素是a,T[3]所对应的next值是1,1对应的元素是a,a与a相同,则T[4]对应的next值就是T[3]的next值+1 ,next[4] = 2;

下标123456789101112
模式串 Tababaaababaa
next[ ]0112

4、看第五位,也就是T[5],看T[5]的前一位T[4]对应元素是b,T[4]所对应的next值是2,2对应的元素是b,b与b相同,则T[5]对应的next值就是T[4]的next值+1 ,next[5] = 3;

下标123456789101112
模式串 Tababaaababaa
next[ ]01123

5、看第六位,也就是T[6],看T[6]的前一位T[5]对应元素是a,T[5]所对应的next值是3,3对应的元素是a,a与a相同,则T[6]对应的next值就是T[5]的next值+1 ,next[6] = 4;

下标123456789101112
模式串 Tababaaababaa
next[ ]011234

6、看第七位,也就是T[7],看T[7]的前一位T[6]对应元素是a,T[6]所对应的next值是4,4对应的元素是b,a与b不同,则向前继续寻找next值,找到T[4]对应的next值是2,2对应的元素是b,a与b不同,继续向前寻找next值,T[2]对应的next值是1,1对应的元素是a,a与a相同,则T[7]对应的next值就是T[2]的 next值 +1,next[7] = 2;

下标123456789101112
模式串 Tababaaababaa
next[ ]0112342

7、看第八位,也就是T[8],看T[8]的前一位T[7]对应元素是a,T[7]所对应的next值是2,2对应的元素是b,a与b不同,则向前继续寻找next值,T[2]对应的next值是1,1对应的元素是a,a与a相同,则T[7]对应的next值就是T[2]的 next值 +1,next[8] = 2;

下标123456789101112
模式串 Tababaaababaa
next[ ]01123422

8、看第九位,也就是T[9],看T[9]的前一位T[8]对应元素是b,T[8]所对应的next值是2,2对应的元素是b,b与b相同,则T[9]对应的next值就是T[8]的 next值 +1,next[9] = 3;

下标123456789101112
模式串 Tababaaababaa
next[ ]011234223

9、看第十位,也就是T[10],看T[10]的前一位T[9]对应元素是a,T[9]所对应的next值是3,3对应的元素是a,a与a相同,则T[10]对应的next值就是T[9]的 next值 +1,next[10] = 4;

下标123456789101112
模式串 Tababaaababaa
next[ ]0112342234

10、看第十一位,也就是T[11],看T[11]的前一位T[10]对应元素是b,T[10]所对应的next值是4,4对应的元素是b,b与b相同,则T[11]对应的next值就是T[10]的 next值 +1,next[11] = 5;

下标123456789101112
模式串 Tababaaababaa
next[ ]01123422345

11、看第十二位,也就是T[12],看T[12]的前一位T[11]对应元素是a,T[11]所对应的next值是5,5对应的元素是a,a与a相同,则T[12]对应的next值就是T[11]的 next值 +1,next[12] = 6;

下标123456789101112
模式串 Tababaaababaa
next[ ]011234223456

注意:这两种方式的细微差别,整体思路一致,注意next起始位置以及没有找到与前一位元素相同的元素时,next赋值问题,可赋值0或1,根据自己实际情况选择

代码实现

第一种:字符数组下标从0开始的代码如下:

/**
 * 求next数组 :字符数组下标从0开始
 * next数组是模式串的部分匹配值整体右移一位,第一位赋值-1得到的数组
 *  注意:若字符数组下标从1开始,则
 *  next数组即是 模式串的部分匹配值整体右移一位,第一位赋值-1,数组整体再+1 所得到的数组
 *
 */

void getNext(char T[],int TLength) {
    int next[TLength];
    next[0] = -1;
    printf("next[0] = %d \n", next[0]);
    int i = 0, j = -1;//i表示数组下标,初始化为0;j表示next数组的值,初始化为-1
    while (i < TLength -1) {
        /**
         * ①若j=-1表示没有找到相同的元素,所求next值应置为0
         * ②若T[i] == T[j] 表示找到了相等的元素,此时找到的这个位置的next值+1就是所求next值
         */
        if (j == -1 || T[i] == T[j]) {
            i++;
            j++;
            next[i] = j;
            printf("next[%d] = %d \n",i, next[i]);
        }else{
            j = next[j] ;
        }
    }
}
int main(){
    char T[] = {'a','b','a','b','a','a','a','b','a','b','a','a'};
    int TLength = 12;
    getNext(T,12);
    return 0;
}

测试结果:

next[0] = -1
next[1] = 0
next[2] = 0
next[3] = 1
next[4] = 2
next[5] = 3
next[6] = 1
next[7] = 1
next[8] = 2
next[9] = 3
next[10] = 4
next[11] = 5

第二种:字符数组下标从1开始的代码如下:

void getNext(char T[],int TLength) {
    int next[TLength];
    next[1] = 0;
    printf("next[1] = %d \n", next[1]);
    int i = 1, j = 0;//i表示数组下标,初始化为1;j表示next数组的值,初始化为0
    while (i < TLength - 1) {
        /**
         * ①若j=0表示没有找到相同的元素,所求next值应置为1
         * ②若T[i] == T[j] 表示找到了相等的元素,此时找到的这个位置的next值+1就是所求next值
         */
        if (j == 0 || T[i] == T[j]) {
            i++;
            j++;
            next[i] = j;
            printf("next[%d] = %d \n",i, next[i]);
        }else{
            j = next[j] ;
        }
    }
}
int main(){
    char T[] = {'*','a','b','a','b','a','a','a','b','a','b','a','a'};
    int TLength = 13;
    getNext(T,13);
    return 0;
}

测试结果:

next[1] = 0
next[2] = 1
next[3] = 1
next[4] = 2
next[5] = 3
next[6] = 4
next[7] = 2
next[8] = 2
next[9] = 3
next[10] = 4
next[11] = 5
next[12] = 6

注意:这两种方式的细微差别,整体思路一致,注意next起始位置以及没有找到与前一位元素相同的元素时,next赋值问题,可赋值0或1,根据自己实际情况选择

 类似资料: