HDOJ--4821--String【弦hash】

聯系：http://acm.hdu.edu.cn/showproblem.php?pid=4821

題意：給一個字元串，選m個長度為l的子串組成新的串。要求這m個子串互不同樣，問有多少種組合。

字元串hash題目，曾經沒做過，做這道之前還用bkdrhash做了兩道簡單的題目。POJ1200和HDU1800。

用base數組記錄乘了幾個seed，base[i]表示seed^i，這個數組在之後計算子串hash值的時候會用到，先預處理一遍節省時間。

假設字元串從前往後hash。則hash[ i ] - hash[ i - l ] * base[ l ] 就是子串 [ i - l , i ] 的hash值，而從後往前hash的話 hash[ i ] - hash[ i + l ] * base[ l ] 就是子串 [ i , i + l ] 的hash值。

推導過程：以從前往後hash為例。如果字元串abab，子串長度2。則

i = 4時的hash值( ( ( (0+a)*seed+b ) * seed +a ) * seed + b ) ，

i - l = 2的hash值( (0+a)*seed+b )。乘base[2]之後 ( ( ( (0+a)*seed+b ) * seed  ) * seed  )

二者相減為a * seed + b。就是區間 [ i - l, i ] 相應字母 ab 的hash值。

之後依照每一點枚舉m個l長度的子串，當他們hash值不同一時候就是一個結果。