有關KMP(看毛片)算法中next數組的問題

Koi279 2022-01-07 05:13:44 阅读数:713

kmp 毛片 算法

相信很多小夥伴和我一樣,剛接觸串時覺得還行,BF算法也肯定一看就懂

直到我們遇見了他

else k=next[k];

這一美其名曰 回溯 的步驟,頓時感覺智商不够用了。

講真的《大話數據結構 》這一部分,我看了幾個小時也沒弄明白,

好在看了老污龜(小甲魚)的視頻後有了點思路;

廢話貌似有點多了;先上代碼,例子講解在後面

#include<stdio.h>
void get_next(char* arr,int* next)
{
int i=1,k=0;
next[1]=0;
while(i<9)
{
if(k==0||arr[i]==arr[k])
{
i++;k++;
next[i]=k;
}
else k=next[k];
}
}
int main()
{
char arr[100]="0ababaaaba";
int next[100];
get_next(arr,next);
for(int i=1;i<=9;i++)
printf("%d ",next[i]);
return 0;
} 

我們來舉個栗子。

1 2 3 4 5 6 7 8 9 
a b a b a a a b a

這是一個字符串,我們來求他的next數組。

①當j=1時, next [1]=0

②當j=2時, j 到 j-1 ,就只有一個字符“a”,顯然next [2]=1

③當j=3時,同上 next [3] =1
④當j=4時, j 由1到 j-1 的串是“ aba ”,前綴字符“ a ”與後緩字符“ a ”相等,next [4] =2.
⑤當j=5時, j 油1到 j-1 的串是“ abab ”,由於前綴字符“ ab ”與後級“ ab ”相等,所以 next [5] =3
⑥當j=6時, j 由1到 j-1 的串是“ ababa ”,由於前綴字符“ aba ”與後綴“ aba ”相等,所以next [6] =4
⑦當j=7時,j由1到 j-1 的串是“ ababaa ”,由於前綴字符“ ab ”與後綴“ aa ”並不相,只有“ a ”相等,所以 next [7] =2
⑧當j=8時,由1到 j-1 的串是“ ababaaa ”,也只有“ a ”相等,所以 next [8] = 2
の當j=9時,由1到 j-1 的串是“ ababaaab ”,由於前綴字符“ ab ”與後綴“ ab ”相所以 next [9]=3.

所以:

 j 1 2 3 4 5 6 7 8 9
串 a b a b a a a b a
next[j] 0 1 1 2 3 4 2 2 3

代碼也比較簡單,相信大家應該也只對 else k=next[k]; 這一步會有疑惑

這裏我們得先明白 我們所求的 next[k] 是啥

如果我們把查找字符串比喻為砍柴的話

next[k] 就是磨刀,即next[k] 就是我們的刀,

他的用處是用空間換時間,讓我們接下來的運算省去一些不必要的過程,

那麼問題就來了

既然能用到後面查找字符串的過程,為什麼不能也用到找next[k] 的過程呢?

next[k] 的大小取决於前後字符串的相似度,

以上述列子來講

 j 1 2 3 4 5 6 7 8 9
串 a b a b a a a b a
next[j] 0 1 1 2 3 4 2 2 3

第六步以後 j=7=a    k=4=b

很明顯 arr [j] ! = arr [k] ,此時k需要回溯,

但具體怎麼回溯呢?

因為j=6,k=3時,arr[j]=a == arr[k]=a 已經相等

即我們現在是67(aa)!= 34(ab)

此時回溯到 k=next[k] 就是通過相似對回到上一個相似的比特置

即k=next[4]=2,

這時我們會發現 arr[1] 和 arr[6] 也是相等的,

但此時12(ab)也不等於 67(aa)

所以k繼續回溯 k=next[2]=1,

此時arr[1] 和 arr[7] 相等,即next[7]=k+1=2.

總之k的回溯就是直接回溯到上一個相似,即有意義去比較的比特置

不然你就得先k=3,再k=2;

顯然,我們沒必要去做一些無用的事情來判斷k=3的情况。

最後,我們再來看看上述程序運行的結果和我們算的一樣不

 不錯不錯,是一樣的(我不尷尬就不會尷尬~~)

版权声明:本文为[Koi279]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/01/202201070513444307.html