Hash在信息學競賽中的一類應用安徽師范大學附屬中學 楊弋Hash在信息學競賽中的一類應用安徽師范大學附屬中學 楊弋1前言Hash前言Hash2前言Hash前言Hash3前言HashCRC32!MD5!SHA-1!More…前言HashCRC32!MD5!SHA-1!More…4例1.多維匹配一維：在一個串中找另一個串第一次出現(xiàn)的位置二維：在一個字符矩陣中找另一個字符矩陣第一次出現(xiàn)的位置如果擴展到k(k≤10)維呢？例1.多維匹配一維：在一個串中找另一個串第一次出現(xiàn)的位置5例1.多維匹配一維的情況：Rabin-Karp算法cacababcabacabO(NM)?例1.多維匹配一維的情況：Rabin-Karp算法cacab6例1.多維匹配一維的情況：Rabin-Karp算法abc×××1pp2abc×××1pp2求和××pp2×p3a×1O(NM)?O(N+M)![]qmodiXpMiXSpfSfMii

][][)()(1-++=+qmod

ú?ùê?épiSSfSleniiSlen][)()(1)(=?=-例1.多維匹配一維的情況：Rabin-Karp算法abc××7例1.多維匹配擴展到二維的情況abaacbbcabac×p2×p×p2×p2×p2×p×p×p×q3q3q3q2q2qq×q2×q例1.多維匹配擴展到二維的情況abaacbbcabac×p28例1.多維匹配擴展到二維的情況×p3×p1××p2×p2p××p3×p4×1例1.多維匹配擴展到二維的情況×p3×p1××p2×p2p×9例1.多維匹配更高維的情況……例1.多維匹配更高維的情況……10例1.多維匹配傳統(tǒng)算法O(k(N+M))難以理解相對實現(xiàn)困難多維Rabin-KarpO(kN+M)易于理解易于編寫，不易出錯例1.多維匹配傳統(tǒng)算法多維Rabin-Karp11例1.多維匹配回顧：我們是怎么計算出Hash值的？部分和？兩端增加或者刪除一位后的Hash值計算兩個串連接后的串的Hash值O(1)O(1)線段樹！SparseTable!分塊！預處理！平衡樹！例1.多維匹配回顧：我們是怎么計算出Hash值的？部分和？兩12例2.樹和圖的同構有根樹=≠例2.樹和圖的同構有根樹=≠13例2.樹和圖的同構有根樹例2.樹和圖的同構有根樹14例2.樹和圖的同構有根樹對每一個子樹計算一個Hash值……12341234123412341234×131=1417(mod2081)1417141712341234(mod2081)((×557)xor×557)xor924×131=3461417141734668例2.樹和圖的同構有根樹對每一個子樹計算一個Hash值……115例2.樹和圖的同構有根樹68516≠≠例2.樹和圖的同構有根樹68516≠≠16例2.樹和圖的同構有根樹O(nlogn)可以給出具體對應方案可以使用Hash表在O(1)時間內查詢例2.樹和圖的同構有根樹O(nlogn)可以給出具體對應17例2.樹和圖的同構有根樹，另一種辦法樹→串23010010子樹的順序？字母序？按Hash值排序！例2.樹和圖的同構有根樹，另一種辦法樹→串23010010子18例2.樹和圖的同構無根樹f(u,v)表示以u為v的父親節(jié)點時以v為根的子樹的Hash值uv例2.樹和圖的同構無根樹f(u,v)表示以u為v的父親節(jié)點時19例2.樹和圖的同構無根樹類似地，有根森林，甚至任意圖的同構問題也是可以使用Hash函數解決的例2.樹和圖的同構無根樹類似地，有根森林，甚至任意圖的同構問20總結Hash的本質Hash信息量大不易比較方便高效地比較“概括”化繁為簡總結Hash的本質Hash信息量大方便高效地比較“概括”21總結正確性優(yōu)美性有所舍棄？效率簡潔擴展性有所收獲！題目適合理想的算法自己總結正確性優(yōu)美性有所舍棄？效率簡潔擴展性有所收獲！題目適合理22結束謝謝！結束謝謝！23例2.樹和圖的同構為什么不直接用Rabin-Karp那樣的先乘后加？Leaf*(p2+p+1)*q*(p+1)*q(Leaf*(p+1)*q*p+Leaf*(p3+p2+p+1)*q)*q?的可能為==例2.樹和圖的同構為什么不直接用Rabin-Karp那樣的先24Hash在信息學競賽中的一類應用安徽師范大學附屬中學 楊弋Hash在信息學競賽中的一類應用安徽師范大學附屬中學 楊弋25前言Hash前言Hash26前言Hash前言Hash27前言HashCRC32!MD5!SHA-1!More…前言HashCRC32!MD5!SHA-1!More…28例1.多維匹配一維：在一個串中找另一個串第一次出現(xiàn)的位置二維：在一個字符矩陣中找另一個字符矩陣第一次出現(xiàn)的位置如果擴展到k(k≤10)維呢？例1.多維匹配一維：在一個串中找另一個串第一次出現(xiàn)的位置29例1.多維匹配一維的情況：Rabin-Karp算法cacababcabacabO(NM)?例1.多維匹配一維的情況：Rabin-Karp算法cacab30例1.多維匹配一維的情況：Rabin-Karp算法abc×××1pp2abc×××1pp2求和××pp2×p3a×1O(NM)?O(N+M)![]qmodiXpMiXSpfSfMii

][][)()(1-++=+qmod

ú?ùê?épiSSfSleniiSlen][)()(1)(=?=-例1.多維匹配一維的情況：Rabin-Karp算法abc××31例1.多維匹配擴展到二維的情況abaacbbcabac×p2×p×p2×p2×p2×p×p×p×q3q3q3q2q2qq×q2×q例1.多維匹配擴展到二維的情況abaacbbcabac×p232例1.多維匹配擴展到二維的情況×p3×p1××p2×p2p××p3×p4×1例1.多維匹配擴展到二維的情況×p3×p1××p2×p2p×33例1.多維匹配更高維的情況……例1.多維匹配更高維的情況……34例1.多維匹配傳統(tǒng)算法O(k(N+M))難以理解相對實現(xiàn)困難多維Rabin-KarpO(kN+M)易于理解易于編寫，不易出錯例1.多維匹配傳統(tǒng)算法多維Rabin-Karp35例1.多維匹配回顧：我們是怎么計算出Hash值的？部分和？兩端增加或者刪除一位后的Hash值計算兩個串連接后的串的Hash值O(1)O(1)線段樹！SparseTable!分塊！預處理！平衡樹！例1.多維匹配回顧：我們是怎么計算出Hash值的？部分和？兩36例2.樹和圖的同構有根樹=≠例2.樹和圖的同構有根樹=≠37例2.樹和圖的同構有根樹例2.樹和圖的同構有根樹38例2.樹和圖的同構有根樹對每一個子樹計算一個Hash值……12341234123412341234×131=1417(mod2081)1417141712341234(mod2081)((×557)xor×557)xor924×131=3461417141734668例2.樹和圖的同構有根樹對每一個子樹計算一個Hash值……139例2.樹和圖的同構有根樹68516≠≠例2.樹和圖的同構有根樹68516≠≠40例2.樹和圖的同構有根樹O(nlogn)可以給出具體對應方案可以使用Hash表在O(1)時間內查詢例2.樹和圖的同構有根樹O(nlogn)可以給出具體對應41例2.樹和圖的同構有根樹，另一種辦法樹→串23010010子樹的順序？字母序？按Hash值排序！例2.樹和圖的同構有根樹，另一種辦法樹→串23010010子42例2.樹和圖的同構無根樹f(u,v)表示以u為v的父親節(jié)點時以v為根的子樹的Hash值uv例2.樹和圖的同構無根樹f(u,v)表示以u為v的父親節(jié)點時43例2.樹和圖的同構無根樹類似地，有根森林，甚至任意圖的同構問題也是可以使用Hash函數解決的例2.樹和圖的同構無根樹類似地，有根森林，甚至任意圖的同構問44總結Hash的本質Hash信息量大不易比較方便高效地比較“概括”化繁為簡總結Hash的本質Hash信息量大方便高效地比較“概括”45總結正確性優(yōu)美性有所舍棄？效率簡潔擴展性有所收獲！