1樓：一腔孤勇
KMP演算法中，如何手動求next陣列和nextval陣列？
首先我們要理解next陣列的意義，為了實現更加高效的字元匹配，next陣列是用來尋找字串陣列內部的自身的一種規律，利用字串內部的一種相似性，來優化字串陣列匹配演算法。所以才需要計算這麼乙個next陣列來幫助演算法更好的實現字串匹配。
next陣列的計算方式邏輯上稍微複雜，初學者可能很難看懂，所以首先要理解，為什麼要計算next陣列以及更加優化的nextval陣列。
假如有這樣一串字串
1 2 3 4 5 6
a a a a a a
這可以說是乙個字串間規律最強的乙個陣列了吧，讓我們來手動模擬一下。
首先預設第一位是0，第二位是1，從第3位開始求，比較第3-1位和next[3-1]的字元是否相同，若相同，則next[3]=next[2]+1
所以第3位的值就是2.那麼依此類推就可以得到，這個字串的next陣列為
1 2 3 4 5 6
a a a a a a
0 1 2 3 4 5
總結來看就是相同就在他的next陣列值加1.
那麼有這樣乙個字串那
1 2 3 4 5 6
a b c d e f
預設給出第1位為0 第二位為1 ，發現全都不一樣,可以說毫無相關性了，所以next陣列為
1 2 3 4 5 6
a b c d e f
0 1 1 1 1 1
這兩種極端情況可以讓大家初步了解一下計算next陣列的方法，起碼可以初步理解一下next陣列的意義。但是這還不完善。
下面介紹一到北郵2023年考研真題
1 2 3 4 5 6 7 8
a b a a b c a c
0 1 1 2 2 3 1 2
這是乙個考試常見的字串，是如何計算的那？
第n位：next[n]的值來自於第n-1位的字元，通過跟第next[n-1]位字元比較，如果相同next[n]=next[n-1]+1,如果不相同，就跟第next[next[n-1]]位的字元比較，就這樣迭代直到相同的時候，加上1，如果實在沒有，就為1.
這一段話可能很難理解，逐位分析。
讓我們從依次來看：
第3位：第2位和第1位比較，不相同所以為1
第4位：第3位和第1位比較，相同，所以為2
第5位：第4位和第2位比較，不相同，和第1位比較，相同，所以為2
第6位：第5位和第2位比較， 相同，所以為3
第7位：第6位和第3位比較，不同，和第1位比較，不同，所以為1
第8位：第7位和第1位比較，相同，所以為2.
這就是next陣列的手動計算方法。
接下來介紹如何根據next陣列計算nextval陣列
nextval是在next陣列的基礎上優化演算法，避免不必要的浪費。其實我也不太理解nextval的具體原理，現只能介紹一下如何計算。
依舊用上面北郵的真題為例，其真題本身求的就是nextval陣列
現在我們已經有了next陣列：
1 2 3 4 5 6 7 8
a b a a b c a c
0 1 1 2 2 3 1 2
現在通過next陣列計算nextval陣列，nextval陣列與next相反，是找不同，
1 2 3 4 5 6 7 8
a b a a b c a c
0 1 1 2 2 3 1 2
0 1 0 2 1 3 0 2
第1位：必為0
第2位：第2位next值為1，所以第2位和第1位比較，不同，為第2位的next 值1
第3位：第3位next值為1，所以第3位和第1位比較，相同，因為到第1位了，所以為0
第4位：第4位next值為2，所以第4位和第2位比較，不同，就為第4位next值2
第5位：第5位next值為2，所以第5位和第2位比較，相同，則繼續，第2位和第1位不同，則為第2位的next值1
第6位：第6位next值為3，所以第6位和第3位比較，不同，就為第6位的next值3
第7位：第7位next值為1，所以第7位和第1位比較，相同，則為0
第8位：第8位next值為2，所以第8位和第2位比較，不同，則為第8位的next值2
【簡而言之】第n位nextval陣列值就是，讓第n位字元和第next[n]位比較，不同，則nextval[n]=next[n],如果相同，則比較第next[next[n]]位和第next[n]位比較，如果不同，則nextVal[n]=next[next[n]].就是這樣的計算方式。
Sedgewick的演算法4中的KMP演算法有不少細節我看不懂，請大家幫我下？
Ben Shi 書中這個地方確實講解的有點不清楚 1.匹配的情況下狀態值是j 1，這個很容易理解，那麼需要搞清楚的就是不匹配的情況怎麼辦。2.不匹配只能從第二個字元 pat.charAt 1 開始重新進行匹配嘗試，因為當前就是從第乙個字元開始匹配失敗的，所以作者說 忽略首字母是因為模式需要右移一位 ...
查詢乙個陣列中字元出現最多頻率的演算法？
因為覺得這種複雜度非常的不科學.所以我Google了一下,然後在stackoverflow上找到了乙個問題.algorithm Find mode of a multiset in given time bound most multiplicity 所以我想你要問的複雜度應該是才對.那個演算法基本...
php如何對這樣的陣列取出鍵名 演算法題卡住了
樂色 php data 1 3 2 4 5 1,10 11 1,9 2 4 5 1,10 11 1,18 4 5 1,print r data keyStack result function fetchKey item else fetchKey data print r result 輸出 Ar...