KMP演算法的C++實作，解決下標0和總是輸出負數(需要完整代碼可在評論區評論，會及時回復)
個人第一次學習資料結構，請各路大神鍵下留情，另外由于等級不夠，無法上傳代碼，需要完整代碼，可在評論區評論，會及時回復，
《大話資料結構》中KMP模式匹配演算法，下標從1開始，個人三天前才開始學習資料結構，看到此章節，停留了兩天，對自身遇到的問題進行錯題記錄，
解決下標0的問題
大話資料結構中，求取模式串next陣列的原始碼如下
可以明顯得知，該方法是以下標“1”為起始，如果在C++中，直接復制此段代碼，會出現如下情況：
總結問題即為：無法識別模式串的下標0是否與主串匹配，單純通過判斷下標1之后的模式串來進行匹配，顯而易見時錯誤的，
next陣列的解決辦法
由于if條件中，存在t[ i ] == t[ j ]，因此，將各個數字-1即可，
我的思路是這樣：
1.下標從1開始時，第一個比較式為t[ 2 ] 與 t[ 1 ]，目的讓第一個比較式變為t[ 1 ] 與 t[ 0 ]，
2.下標從1開始時，原式會由于j=0，而比較t[ 2 ] 與 t[ 1 ]，那么，若條件為j= -1，則會比較
t[ 1 ] 與 t[ 0 ]，
多拿筆寫寫，畫畫，思路就出來了，
next陣列下標從0開始，在最終匹配時總是輸出錯誤
這個錯誤的原因，是由于while回圈條件導致的，接著看，
即便next陣列改為從0開始，依然會輸出錯誤，此時要注意第36行，回圈條件是：int型與size_t型的比較，而當出現int值為-1時，會直接跳出回圈，導致錯誤，
如果不信，可以設定如下主串和模式串，并加一行判斷代碼，判斷串和判斷代碼如下圖
由前面的KMP演算法可知，當s[0] != t[0]，且ix != -1,會進入ix = next[ix] = next[0] = -1;
接著++id，++ix，然而此時的除錯結果并沒有輸出第42行的內容，而是直接跳出while回圈，
也就是說，當ix = -1時，由于不滿足回圈判斷條件而直接輸出，導致結果出錯，
while判斷條件解決辦法
（注意：上圖的i = id，j = ix，實質上沒有區別）將s.size(),t.size()都定義為int型別變數，即可成功輸出
補全綠色注釋，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/173316.html
標籤：java
下一篇：順序表ADT模板設計及簡單應用：將順序表中前 m 個元素和后 n 個元素進行互換（資料結構OJ練習）（樣例4553 WA）