next數(shù)組兩種求法
一缆娃、求法的文字描述
（1）第一種求法：根據(jù)前一個(gè)字符的next值求字符串記作 p弃锐；next 數(shù)組記作 next粪躬；
約定：
下標(biāo)從 1 開(kāi)始算担败，注意，不是從 0 開(kāi)始算
字符串長(zhǎng)度 >2
1）第一個(gè)字母的 next 值置 0 （nesxt[1] = 0）短蜕，第二個(gè)字母的 next 值置 1（next[2] = 1）
2）從第 3 個(gè)開(kāi)始氢架，計(jì)算第 i 個(gè)位置的 next 值時(shí)傻咖，檢查
p[i-1]== p[next[i-1]] ?（即這兩個(gè)值是否相等）
解釋?zhuān)旱?i 個(gè)位置的前一個(gè)位置的值（即 p[i-1]）與以該位置的next 值（即 next[i-1]）為下標(biāo)的值（即 p[next[i-1]]）是否相等
若相等朋魔，則 next[i] = next[i-1] + 1
若不等，則繼續(xù)往回找卿操，檢查
p[i-1]== p[next[next[i-1]]] ?
若相等警检，則 next[i] = next[next[i-1]] + 1
若不等，則繼續(xù)往回找害淤，直到找到下標(biāo)為 1 還不等（即字符串第一個(gè)元素）扇雕，直接賦值 next[i] = 1
（2）第二種求法：根據(jù)最大公共元素長(zhǎng)度求
首先附上講解的博文地址，里面有詳細(xì)講解
- 1）算出每一個(gè)字母前綴后綴的最大公共元素長(zhǎng)度
- 2）最大公共元素長(zhǎng)度整體向后移動(dòng)一個(gè)長(zhǎng)度窥摄，最前面的元素值填 -1镶奉，即為 next 數(shù)組的第一版本
- 3）（如果你需要的 next 數(shù)組第一個(gè)值為 -1，這步就可以省略了）next 數(shù)組的每一個(gè)值分別+1崭放，即求得 next 數(shù)組哨苛。
前綴后綴的最大公共元素長(zhǎng)度
前綴：即從第一個(gè)字母開(kāi)始往后看到最后一個(gè)字母（不包括）為止的字符串的以第一個(gè)字母開(kāi)頭的子串(比如 "abab" 的前綴有a,ab,aba);
后綴：即從最后一個(gè)字母開(kāi)始往前看到第一個(gè)字母（不包括）為止的字符串的以最后一個(gè)字符為末尾的子串(比如 "abab" 的后綴有b,ab,bab);
-
最大公共子串長(zhǎng)度：也就是前綴和后綴擁有的相同子串的最大長(zhǎng)度;
以"abab"為例：
| 模式串的各個(gè)子串 | 前綴 | 后綴 | 最大公共元素長(zhǎng)度 |
|---|---|---|---|
| a | 空 | 空 | 0 |
| ab | a | b | 0 |
| aba | a,ab | a,ba | 1 |
| abab | a,ab,aba | b,ab,bab | 2 |
二、實(shí)例
現(xiàn)在求字符串 P = "ababaaababaa"
(1) 對(duì)于上面的第一種解法
- 初始化
| P | a | b | a | b | a | a | a | b | a | b | a | a |
| 下標(biāo) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| next | 0 | 1 |
2)求下標(biāo)為3的字符的next值
- P[3-1] = P[2] = 'b';
- next[3-1] = next[2] = 1 ;
- P[next[3-1]] = P[1] = 'a';
- P[3-1] != P[next[3-1]] 币砂，但是此時(shí)已經(jīng)回溯到了第一個(gè)元素
- ∴ 直接P[3] = 1 ;
| P | a | b | a | b | a | a | a | b | a | b | a | a | |
| 下標(biāo) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | |
| next | 0 | 1 | 1 |
3）求下標(biāo)為 4 的字符的 next 值
- P[4-1] = P[3] = 'a';
- next[4-1] = next[3] = 1 ;
- P[next[4-1]] = P[1] = 'a';
- P[4-1] == P[next[4-1]] ;
- ∴ next[4] = next[4-1] + 1 = 2 ;
| P | a | b | a | b | a | a | a | b | a | b | a | a | |
| 下標(biāo) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | |
| next | 0 | 1 | 1 | 2 |
4）求下標(biāo)為 5 的字符的 next 值
- P[5-1] = P[4] = 'b';
- next[5-1] = next[4] = 2 ;
- P[next[5-1]] = P[2] = 'b';
- P[5-1] == P[next[5-1]] ;
- ∴ next[5] = next[5-1] + 1 = 3 ;
| P | a | b | a | b | a | a | a | b | a | b | a | a |
| 下標(biāo) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| next | 0 | 1 | 1 | 2 | 3 |
5）求下標(biāo)為 6 的字符的 next 值
- P[6-1] = P[5] = 'a';
- next[6-1] = next[5] = 3;
- P[next[6-1]] = P[3] = 'a';
- P[6-1] == P[next[6-1]];
- 所以 next[6] = next[6 - 1] + 1 = 4;
| P | a | b | a | b | a | a | a | b | a | b | a | a |
| 下標(biāo) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| next | 0 | 1 | 1 | 2 | 3 | 4 |
6）求下標(biāo)為 7 的字符的 next 值
- P[7-1] = P[6] = 'a';
- next[7-1] = next[6] = 4;
- P[next[7-1]] = P[4] = 'b';
- P[7-1] != P[next[7-1]] 并且現(xiàn)在還沒(méi)有回溯到第一個(gè),繼續(xù)
- next[next[7-1]] = next[4] = 2;
- P[next[next[7-1]]] = P[2] = 'b';
- P[7-1] != P[next[next[7-1]]] 并且現(xiàn)在還沒(méi)有回溯到第一個(gè)建峭，繼續(xù)
- next[next[next[7-1]]] = 1;
- P[next[next[next[7-1]]] = 'a';
- P[7-1] == P[next[next[next[7-1]]]];
- 所以next[7] = next[next[next[7-1]]] + 1 = next[2] + 1 = 2
| P | a | b | a | b | a | a | a | b | a | b | a | a |
| 下標(biāo) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| next | 0 | 1 | 1 | 2 | 3 | 4 | 2 |
7）求下標(biāo)為 8 的字符的 next 值
- P[8-1] = P[7] = 'a';
- next[8-1] = next[7] = 2;
- p[next[8-1]] = P[2] = 'b';
- P[8-1] != P[next[8-1]] 并且現(xiàn)在還沒(méi)有回溯到第一個(gè),繼續(xù)
- next[next[8-1]] = 1;
- P[next[next[8-1]]] = p[1] = 'a';
- P[8-1] == P[next[next[8-1]]];
- 所以next[8] = next[next[8-1]] + 1 = 2;
| P | a | b | a | b | a | a | a | b | a | b | a | a |
| 下標(biāo) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| next | 0 | 1 | 1 | 2 | 3 | 4 | 2 | 2 |
8）求下標(biāo)為 9 的字符的 next 值
- 推導(dǎo)過(guò)程同4) => next[10] = next[10-1] + 1 = 4 ;
| P | a | b | a | b | a | a | a | b | a | b | a | a |
| 下標(biāo) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| next | 0 | 1 | 1 | 2 | 3 | 4 | 2 | 2 | 3 |
9）求下標(biāo)為 10 的字符的 next 值
- 推導(dǎo)過(guò)程同4) => next[10] = next[10-1] + 1 = 4 ;
| P | a | b | a | b | a | a | a | b | a | b | a | a |
| 下標(biāo) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| next | 0 | 1 | 1 | 2 | 3 | 4 | 2 | 2 | 3 | 4 |
10）求下標(biāo)為 11 的字符的 next 值
推導(dǎo)過(guò)程同4) => next[11] = next[11-1] + 1 = 5 ;
| P | a | b | a | b | a | a | a | b | a | b | a | a |
| 下標(biāo) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| next | 0 | 1 | 1 | 2 | 3 | 4 | 2 | 2 | 3 | 4 | 5 |
11）求下標(biāo)為 12 的字符的 next 值
推導(dǎo)過(guò)程同4) => next[12] = next[12-1] + 1 = 6;
| P | a | b | a | b | a | a | a | b | a | b | a | a |
| 下標(biāo) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| next | 0 | 1 | 1 | 2 | 3 | 4 | 2 | 2 | 3 | 4 | 5 | 6 |
(2) 對(duì)于上面的第二種解法
1）算出每一個(gè)字母前綴后綴的最大公共子串長(zhǎng)度
| P | a | b | a | b | a | a | a | b | a | b | a | a |
| 前后綴最大公共子串長(zhǎng)度 | 0 | 0 | 1 | 2 | 3 | 1 | 1 | 2 | 3 | 4 | 5 |
2）最大公共子串長(zhǎng)度整體向后移動(dòng)一個(gè)長(zhǎng)度，最前面的元素值填 -1决摧，即為 next 數(shù)組的第一版本
| P | a | b | a | b | a | a | a | b | a | b | a | a |
| 前后綴最大公共子串長(zhǎng)度 | -1 | 0 | 0 | 1 | 2 | 3 | 1 | 1 | 2 | 3 | 4 | 5 |
三亿蒸、代碼實(shí)現(xiàn)
void getnext(seqstring *p, int next[])
{
int i, j;
next[0] = -1;
i = 0; j = -1;
while (i < p->length)
{
if (j == -1 || p->str[i] == p->str[j])
{
++i;
++j;
next[i] = j;
}
else
j = next[j];
}
for (i = 0; i < p->length; i++)
printf("%d ", next[i]);
}
四凑兰、驗(yàn)證
#include "stdio.h"
#include "stdlib.h"
#define MAXSIZE 100
typedef struct {
char str[MAXSIZE];
int length;
}seqstring;
void getnext(seqstring *p, int next[])
{
int i, j;
next[0] = -1;
i = 0; j = -1;
while (i < p->length)
{
if (j == -1 || p->str[i] == p->str[j])
{
++i;
++j;
next[i] = j;
}
else
j = next[j];
}
for (i = 0; i < p->length; i++)
printf("%d ", next[i]);
}
int main()
{
int i, j = 0;
seqstring str;
str.length = 0;
printf("請(qǐng)輸入字符串的長(zhǎng)度：\n");
scanf("%d", &j);
getchar();
for (i = 0; i < j; i++)
{
scanf("%c", &str.str[i]);
str.length++;
}
int next[] = { 0 };
getnext(&str, next);
system("pause");
return 0;
}
