本題為教學題所以很裸很水。
你有聽過 Rabin-Karp fingerprint algorithm 嗎？這是一種 string hash 演算法，常用於做字串匹配，由於它可以在 $O(n)$ 時間預處理並在 $O(1)$ 時間查詢任一子字串的 hash 值，往往可以做到確定性演算法中要用複雜的 suffix array 之類的演算法才能做到的事情。
然而，既然是 hash 就會有碰撞問題，估計碰撞機率並在一開始就判斷好要怎麼實作是很重要的。假設 rabin-karp 的模數為 $M$ ，已知兩個字串碰撞的機率約為 $\frac{1}{M}$ ，做 $N$ 次兩字串相等判斷的碰撞機率則為 $\frac{N}{M}$，而特別的是如果是一個大小 $N$ 的字串集合，那麼根據生日問題，如果 $M=\Omega(N^2)$ 就會有高機率產生碰撞。換句話說一個大小約為 $30000$ 的集合在常見 int 範圍內的模數就有很高的機率會產生碰撞了。
為了避免這樣的問題，因此存在好幾種提升模空間 $M$ 的大小的方法。第一種最直觀的想法就是令模數 $M$ 是 long long 等級的數字，然而問題是運算會到 int128 數量級導致運算速度極慢通常會得到 TLE。第二種常見的作法則是 multiple (double) hash，也就是用兩組以上的 int 範圍 hash 參數來組成 hash tuple 來讓模空間 $M=m_1m_2$ 大約是 long long 的數量級，然而 hash 中所使用的模運算效率很差，做 multiple hash 也會直接讓運算量倍增影響效率有時沒寫好也會得到 TLE。
那麼是否存在方法可以有 long long 等級的模空間又有高運算效率呢？答案是有的。既然第一種方法的瓶頸是在運算量級會溢位，且兩種方法都存在模運算很慢的問題，那麼使用自然溢位就兩個問題都能解決了。使用自然溢位的話直接省掉了模運算，又不用考慮溢位問題可以安心的做任意運算，如果型態設為 (unsigned) long long 的話就可以有 long long 數量級又效率很高的 hash 方法了，而且實作上甚至不用考慮模運算的問題寫起來更為簡單。心動不如馬上行動，本題將是裸的大字串集的匹配計數問題。
第一行輸入兩個數字 $N,t$ 代表接下來有 $N$ 個字串以及長度下限 $1\le t\le 2\times 10^5$。
第 $2\sim N+1$ 行每行各有一個非空字串 $S_i$，其中字串只包含小寫英文字母。
$\sum\limits_{i=1}^N {|S_i|-t+2\choose 2}\le 5\times 10^6$ 其中 $n\choose m$ 代表組合數，也就是 $C^n_m$ 的意思。換句話說也就是總子字串數量不超過 $5\times 10^6$
$\sum\limits_{i=1}^N |S_i|\le 5\times 10^6$
假設可重集合 $S=\{S_i[j\dots k]|1\le i\le N, 1\le j\le k\le |S_i|, k-j+1\ge t\}$ 也就是所有字串的所有長度至少 $t$ 的子字串所組成的可重集合，並令 $S'$ 為 $S$ 的去重集合。
那麼請輸出一個整數代表 $\sum\limits_{s\in S'}{\text{multiplicity of s in S}\choose 2}$ 。換句話說也就是輸出對於每個相異字串，其出現次數取2的總和。也等價於所有相同字串出現在相異位置的配對數量總和。
3 1 abc aba ba
11
你從本題學到了什麼呢XD
建議可以各種方法都試試看來比較各種方法的差異、優劣等XD
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||