前綴和演算法

❶ 這個為什麼前綴和後綴演算法都等於8 具體怎麼算的

前綴運算：
÷+*+1*2 4 5 3*1 6
=÷+*+1*2 4 5 3 6
=÷+*+1 8 5 3 6
=÷+*9 5 3 6
=÷+45 3 6
=÷48 6
=8

後綴運算：
1 2 4 *+5*3+1 6*÷
=1 8+5*3+1 6*÷
=9 5*3+1 6*÷
=45 3+1 6*÷
=48 1 6*÷
=48 6÷
=8

❷ 密碼機前綴為什麼是SJ

首先對於非對稱加密體制，對RSA演算法作了詳細的說明，RSA演算法基於大數模冪乘運算，其運行效率決定了RSA非對稱密碼的性能，文中說明了各種模冪演算法的快速實現方法，並進行比較分析。

其次對於對稱加密體制，以DES（Data Encryption Standard，數據加密標准）演算法和Rijndael演算法為重點，首先對DES和Rijndael演算法的加密原理進行說明，並通過對演算法的分析找出它們的不足之處，如DES演算法，易受選擇明文法攻擊，而Square攻擊法是對Rijndael演算法最有效的攻擊法。

它們的攻擊原理是基於加密系統的不變性，因此本文提出了基於前綴碼的解決方案，因為前綴碼具有很好的解碼特性，通過前綴碼的引入可以對輸入的明文解碼，以此來改變演算法子密鑰的使用順序，從而使加密系統不再固定不變，而是隨著明文的不同而不斷變化，使演算法對攻擊具有很好的抵抗性。

最後對數字簽名過程進行分析，由於MD5演算法已經被破解，所以數字簽名存在著被偽造的隱患。

因此本文提出了基於前綴碼的數字簽名改進方案，通過前綴碼的解碼特性對MD5演算法產生的摘要進行解碼、變換，然後再通過網路傳輸，消除了數字簽名可能被偽造的隱患。

❸ kmp求next數組

KMP演算法，主要分為2個階段：

• 求next數組。
  

• 字元串匹配

• next數組，就是對給定的「匹配字元串」，求出其每一個子長度字串的「最長前綴和最長後綴相等的長度」。

匹配串，p="aabcaabbaa", 長度n=10。因此子串為sub[10]：



sub[0]="a"sub[1]="aa"sub[2]="aab"sub[3]="aabc"sub[4]="aabca"sub[5]="aabcaa"sub[6]="aabcaab"sub[7]="aabcaabb"sub[8]="aabcaabba"sub[9]="aabcaabbaa"


根據「最長前綴和最長後綴相等的長度」，可以求出對應的next數組是：




next[0]=-1;//"a"next[1]=0;//"aa"next[2]=-1;//"aab"next[3]=-1;//"aabc"next[4]=0;//"aabca"next[5]=1;//"aabcaa"next[6]=-1;//"aabcaab"next[7]=-1;//"aabcaabb"next[8]=0;//"aabcaabba"next[9]=1;//"aabcaabbaa"

2. 利用上部求出的next數組，對t和p進行匹配。要點是：



（1）循環匹配（2）如果整個匹配上，則返回匹配位置。（3）如果當前位置沒有匹配上，則：如果對應next[x]為-1，則跳過整個p的長度；否則，回溯到其前綴位置進行匹配。匹配上，則右移next[x-1]位置；否則，右移next[x]位置。

具體到「多少次字元匹配」，在編制的程序里加上統計的語句，最後輸出。真要一個個字元統計，很容易出錯。

❹ 演算法-KMP

大一下參加學校ACM預備隊集訓的時候首次接觸KMP演算法，當時看了很多介紹文章，仍然不是很理解其實質，只是簡單地套模板AC題目，待大二數據結構與演算法課堂上再聽老師介紹一次，才恍然大悟其實KMP也就是那麼回事嘛。但當初為啥看那麼多文章都沒弄明白呢？正巧最近和朋友聊天時他告訴我他對KMP不是很理解，於是打算自己寫一篇文章，鞏固自己對KMP的認識，也希望能夠幫助更多朋友理解KMP。
在開始之前，需要知曉的概念：

前綴：以原串串頭為自身串頭的子串，如 的前綴有：
後綴：以原串串尾為自身串尾的子串，如 的後綴有：

注意：字元串前後綴都不包括該串本身

給你一個文本串T(Text String)

再給你一個模式串P(Pattern String)

問該模式串是否在文本串中，怎麼找？

一開始只好分別從文本串與模式串的串頭開始逐字母比較

二者相同，再比較T串與P串的下一位

如此反復

如果一直這么順利，兩串對應位置的字元總相同，待P串中最後一個字元也匹配完畢，說明該模式串在文本串中存在，耶( •̀ ω •́ )y超開心，查找結束。但，大多數匹配過程不會如此順利，在該例中，當匹配進行至

很明顯，失配了。現在怎麼辦？按樸素思想，將P串相對T串整體右移一位，重新開始匹配，即

但這種演算法效率無疑是十分低下的。設T串長度N，P串長度M，則樸素演算法時間復雜度為O(MN)

已知的重要信息並沒有被使用——已匹配的字元串前綴

在上例中，當P串最後一個字元匹配失敗時，其已有包含七個字元的 前綴子串S 匹配成功

完全可以利用前綴子串S做點什麼。觀察到在S串

中，有相同前後綴，即下圖藍色部分

而S串各字元又與T串中對應字元相同，即有

當失配發生後，直接將P串右移四位使S串藍色後綴部分對齊T串中藍色前綴部分

從圖中紅框部分繼續嘗試匹配，發現再次失配。這次，已匹配成功的前綴串S為

而在該串中沒有相同的前後綴，只能將P串串頭移至失配處進行比較

再次失配。此時前綴串S為空串，只好如樸素演算法般將P串整體右移一位，重新開始比較

匹配成功。於是又按照之前的步驟往下匹配，直至再次失配或匹配成功

後續步驟同上，不再贅述

上述示例已展現，KMP演算法的精髓在於對已匹配成功的前綴串S的利用

在樸素演算法中，匹配失敗了，T串待匹配字元會回溯

T串原本已匹配至T[7] = 'X'，但是因為失配，需回溯到T[1] = 'b'重新開始匹配

而在KMP演算法中，若P[M]與T[K]匹配失敗，K不會回溯。既然匹配過程是從T[0]開始逐漸向右進行的，至T[K]失配發生時，T[0]至T[K-1]早已匹配過，何必再回溯過去重復匹配呢？於是乎，就如問題引入部分展示般

每當失配發生，我們總是去關注P串中已匹配成功的前綴串S

因為該前綴串是匹配成功的，說明在T串中必定存在與該前綴串相同的子串，記為S'

若S串中存在相同前後綴

則S'串必然也存在此相同前後綴

所以只需將P串右移四位，使得S串的該相同前綴對齊S'串的該相同後綴

再嘗試比較T[7]與P[3]

至於T[7]與P[3]是否能夠匹配另說（當然，本例中一看就知道沒匹配上），但通過對前綴串S的利用，成功省去了P串右移一位、兩位和三位後的無效匹配

繼續深入思考，給定一個具體的P串，其第N位的前綴串S內容是固定的，則S是否存在相同前後綴、相同前後綴的長度與內容也是確定的。換言之，對於一個具體的P串，當其與給定T串匹配至P[N]失配，P串應右移幾位再次與T串進行匹配也是確定的。我們完全可以使用一個數組記錄當P[N]失配後，應當使用N之前的哪一位再來與T串進行匹配，以此提高匹配效率，記該數組為Next數組

定義Next[i] = j表示當P串中第i位失配後，跳轉至P串第j位再次嘗試匹配

還是以之前的P串為例，它的Next數組求出來應為

取下標5為例，其前綴串為

最長相同前後綴為

若P[5]失配，應跳轉至P[1]再次嘗試匹配（最長相同前綴對應P[0]，則取其後一位P[1]，若存在多位，則取最後一位的下一位），P[5]的前一個字元P[4]對應字元'a'，而P[1]前一個字元P[0]同對應字元'a'，保證了P[1]之前字元與T串中對應字元保持匹配。所以Next[5] = 1，其餘下標對應Next數組值同如此求。

特別地，規定Next[0] = -1。而對於除下標0外的任意下標N，Next[N]的含義是 前N-1個已匹配成功的字元構成的前綴串S中，最長相同前後綴長度。 所以若在下標為N處匹配失敗了，則應前往Next[N]所對應的下標處匹配。

具體地，以下圖所示為例，P[6]與T[6]失配

而Next[6] = 2，所以使用P[2]再次嘗試與T[6]進行匹配

當求出P串Next數組後，便可快速進行與T串的匹配

現在問題只剩下如何求Next數組，注意到Next數組既然只與P串本身相關，與文本串T無關，故令P串與自身匹配即可求得

考慮字元串

其Next數組應為

令其與給定文本串相匹配

當匹配進行至

失配，於是跳轉至P[Next[3]] = P[1]處再次嘗試匹配

再度失配，也必然失配

問題在於不該出現P[N] =P[Next[N]]

若P[N] =P[Next[N]]，則P[N]失配後使用P[Next[N]]再次嘗試匹配，由於P[N] =P[Next[N]]，P[N]匹配失敗，P[Next[N]]必然也失敗

因此，若出現P[N] =P[Next[N]]情況，則令Next[N]=Next[Next[N]]

本例中該字元串新Next數組為

當匹配進行至

失配，於是跳轉至P[Next[3]] = P[0]處再次嘗試匹配

省去了之前跳轉至P[1]處的無效匹配

設T串長度M，P串長度N，由於KMP演算法不會回溯，分析易知時間復雜度為O(m+n)

對於P[N]，若其前綴串S含相同前後綴F，且F長度為n（n>1），Next[N]可以取1至n中任意值，為最大化匹配效率考慮，總是取最大相同前後綴以提高效率，節省時間

❺ 前綴、中綴、後綴表達式怎麼畫成二叉樹（不要演算法，不要代碼，寫出怎麼畫就行）

先說二叉樹：
這里的前中後指的根的順序，前的順序是：根左右
中的順序是：左根右
後的順序是：左右根
比如有樹的前序為：ABDHIECFG
中序為：HDIBEACFG
可以畫出整棵樹
你這里想畫出一棵二叉樹，那麼你可以算出他的前綴，中綴可以確定一棵樹，中綴，後綴也可以，前綴，後綴不可以確定一棵樹，單純的前綴，中綴，後綴不可以確定一棵樹
（我也不太確定你的問題問的是什麼）

❻ 圖解KMP字元串匹配演算法

kmp演算法跟之前講的bm演算法思想有一定的相似性。之前提到過，bm演算法中有個好後綴的概念，而在kmp中有個好前綴的概念，什麼是好前綴，我們先來看下面這個例子。

觀察上面這個例子，已經匹配的abcde稱為好前綴，a與之後的bcde都不匹配，所以沒有必要再比一次，直接滑動到e之後即可。
  那如果前綴中有互相匹配的字元呢？

觀察上面這個例子，這個時候如果我們直接滑到好前綴之後，則會過度滑動，錯失匹配子串。那我們如何根據好前綴來進行合理滑動？

  其實就是看當前的好前綴的前綴和後綴是否有匹配的，找到最長匹配長度，直接滑動。鑒於不止一次找最長匹配長度，我們完全可以先初始化一個數組，保存在當前好前綴情況下，最長匹配長度是多少，這時候我們的next數組就出來了。

  我們定義一個next數組，表示在當前好前綴下，好前綴的前綴和後綴的最長匹配子串長度，這個最長匹配長度表示這個子串之前已經匹配過匹配了，不需要再次進行匹配，直接從子串的下一個字元開始匹配。

 我們是否每次算next[i]時都需要每一個字元進行匹配，是否可以根據next[i - 1]進行推導以便減少不必要的比較。
  帶著這個思路我們來看看下面的步驟：
  假設next[i - 1] = k - 1;
  如果modelStr[k] = modelStr[i] 則next[i]=k

如果modelStr[k] != modelStr[i]，我們是否可以直接認定next[i] = next[i - 1]？

通過上面這個例子，我們可以很清晰地看到，next[i]!=next[i-1]，那當modelStr[k]!=modelStr[i]時候，我們已知next[0],next[1]…next[i-1]，如何推導出next[i]呢？
  假設modelStr[x…i]是前綴後綴能匹配的最長後綴子串，那麼最長匹配前綴子串為modelStr[0…i-x]

我們在求這個最長匹配串的時候，他的前面的次長匹配串（不包含當前i的），也就是modelStr[x…i-1]在之前應該是已經求解出來了的，因此我們只需要找到這個某一個已經求解的匹配串，假設前綴子串為modelStr[0…i-x-1],後綴子串為modelStr[x…i-1],且modelStr[i-x] == modelStr[i],這個前綴後綴子串即為次前綴子串，加上當前字元即為最長匹配前綴後綴子串。
代碼實現
  首先在kmp演算法中最主要的next數組，這個數組標志著截止到當前下標的最長前綴後綴匹配子串字元個數，kmp演算法裡面，如果某個前綴是好前綴，即與模式串前綴匹配，我們就可以利用一定的技巧不止向前滑動一個字元，具體看前面的講解。我們提前不知道哪些是好前綴，並且匹配過程不止一次，因此我們在最開始調用一個初始化方法，初始化next數組。
  1.如果上一個字元的最長前綴子串的下一個字元==當前字元，上一個字元的最長前綴子串直接加上當前字元即可
  2.如果不等於，需要找到之前存在的最長前綴子串的下一個字元等於當前子串的，然後設置當前字元子串的最長前綴後綴子串

然後開始利用next數組進行匹配，從第一個字元開始匹配進行匹配，找到第一個不匹配的字元，這時候之前的都是匹配的，接下來先判斷是否已經是完全匹配，是直接返回，不是，判斷是否第一個就不匹配，是直接往後面匹配。如果有好前綴，這時候就利用到了next數組，通過next數組知道當前可以從哪個開始匹配，之前的都不用進行匹配。

❼ 網路前綴長度怎麼計算麻煩寫一下有哪些數字計算

你把IP和掩碼全部換算成二進制，IP中和掩碼中全1的位對應的就是網路號（網路前綴）
沒什麼演算法的

❽ 請教波蘭表達式前綴表達式的演算法

對於一個前綴表達式的求值而言，首先要從右至左掃描表達式，從右邊第一個字元開始判斷，如果當前字元是數字則一直到數字串的末尾再記錄下來，如果是運算符，則將右邊離得最近的兩個「數字串」作相應的運算，以此作為一個新的「數字串」並記錄下來。一直掃描到表達式的最左端時，最後運算的值也就是表達式的值。例如，前綴表達式「- 1 + 2 3「的求值，掃描到3時，記錄下這個數字串，掃描到2時，記錄下這個數字串，當掃描到+時，將+右移做相鄰兩數字串的運算符，記為2+3，結果為5，記錄下這個新數字串，並繼續向左掃描，掃描到1時，記錄下這個數字串，掃描到-時，將-右移做相鄰兩數字串的運算符，記為1-5，結果為-4，所以表達式的值為-4。

❾ 前綴中綴後綴表達式的轉換，能幫一下嗎

思路的話其實很簡單，就是構建一棵二叉樹，根節點和中間節點為運算符，葉子結點為運算數字。如 a + b*c， 構建為二叉樹的話，就如下圖： +a * b c對於該二叉樹，使用不同的遍歷方式就可以得到不同的表達式了。遍歷的代碼很簡單就不多說了。因此，你的問題主要可以分解為3個小問題：1。將後綴表達式轉換為二叉樹 該方法是最簡單的。如a + b*c 的後綴表達式為 bc*a+.處理步驟如下： 1。建立一個棧S
2。從左到右讀後綴表達式，讀到數字就創建葉子節點，節點值為數字值。將節點壓入棧S中，讀到運算符則創建中間節點，並從棧中依次彈出兩個節點分別為Y和X，作為中間節點的左右子節點，然後以「X 運算符 Y」的形式計算機出中間節點的值，再將此中間節點壓加棧S中 3。就重復第二步直至後綴表達式結束，此時棧頂的節點就是二叉樹的根節點了。2。將中綴表達式轉換為二叉樹 按照上一個回答者的方法將中綴表達式轉為後綴表達式，然後調用後綴表達式生成二叉樹的解法即可。3。將前綴表達式轉換為二叉樹 將前綴表達式直接取反即為後綴表達式。 如前綴表達式為+*bca，對應的後綴表達式為acb*+。因此，我們只需要字元串取反，然後調用後綴表達式的方法生成二叉樹即可。