轉站通知

本站已停止更新!!想繼續收看我的新文章的話,請前往我的新Blog - Chino's

2014年3月24日 星期一

STEP5::Problem 0114 : 破:萌娘苦力怕

http://web2.ck.tp.edu.tw/~step5/probdisp.php?pid=0114
字串hash比對。
這題要比對一個字串,其中的比對方式就是題目中說的,環狀相等。
第一就是字串比對時,可以用hash的方法O(1)比對(一般掃一遍是O(n) ),就是把字串當成一種27進位法,從右邊加一位就*27+字元,從左邊加字元就 字元*27的位數次方。因為數字很大,mod一個很大的數字,不過這樣有可能會有不一樣的字串一樣的數字的情況發生(我就遇到了.....),這時可以換一個數字,或是多個數字去比對,越多錯誤率越小。

再來我就從第一個和最後一個開始比對,如果一樣就丟到steak裡,直到最大,再來從stack最上面的值開始繼續比第二段,最後最大值就是暫時的答案。然後,如果答案到n/2還有一段,就一段一段加入第二段,另一端把第一段退回stack裡的第二個位置(因為有可能這樣會有更優解),重複執行直到stack空掉或是超過n/2。