ETH官方钱包

前往
大廳
主題

ZeroJudge - f942: 字串判斷 解題心得

Not In My Back Yard | 2021-06-13 00:00:14 | 巴幣 12 | 人氣 295

題目連結:


題目大意:
輸入有若干列(最多 5000 列),每列給定一個字串(長度不超過 10000 個字元,由數字以及大小寫字母組成)。試問哪兩個字串一樣?請輸出它們兩個為第幾個輸入的字串(從 1 開始數)。

保證只會有一組字串相同。

記憶體限制:15 MB



範例輸入:
1234
5678
5677
5678


範例輸出:
2 4


解題思維:
因為記憶體限制在 15 MB 以內,所以要直接存下所有字串是不可能的。因為最多會有 5000 × 10000 個字元,一個字元佔 1 byte 。所以有可能會超過 47MB 。

因此,我們可以考慮使用許多語言內建的雜湊(Hash)函式。



例如 C++ 在本題會宣告一個 hash <string> 型態的變數作為雜湊器。而雜湊出來的值會是一個 32 位元的無號整數。因此其碰撞(不同內容,但雜湊值相同)發生機率為 1 ÷ (2 ^ 32) 。而本題最多只會有 5000 個字串,所以當兩者雜湊值相同時基本上(本題並沒有太過刁鑽)代表著兩個字串相同,而不是發生碰撞。

因此,我們只需存下每個字串雜湊後的值然後交叉比對即可得出相同字串是哪兩個,輸出它們為輸入第幾個即可。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作