如上圖,先建一個 pre[k] 表示 s[k]==s[k-1]。

 所以當你從 idxk, idxj 往下比較時,順便紀錄 最後面 且 pre[idxk]=false,的位置,下次只要從那裏開始比較就好了。

複雜度 O(n)。

我的code http://snipt.org/Aaav9

 

文章標籤
創作者介紹

jghs1328

jghs1328 發表在 痞客邦 留言(1) 人氣()


留言列表 (1)

發表留言
  • c2251393
  • 這題我看完之後直覺想到用Hash@@
  • 野生國手出現,快拜
    我比較不會hash那些的==

    jghs1328 於 2013/05/18 11:41 回覆