給你一個 ab 字串 s (n<500000),要你找出 最短 且 不是 s 的子字串。

SGU 真的不少這種輕巧的思考題XD。

1. 發現 n < 2^19

2. 答案的長度很明顯是 L=lg(n)。

3. 弄一顆 深度為 L 的二元樹。

4. 往左表示 'a' 右則表示 'b'。

5. 枚舉原字串 s 的 長度為 L 的子字串,遍歷二元樹。

6. 找到最小 沒有 被遍歷的 節點,往回走一遍 即得答案。

複雜度 O(n)

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

 

文章標籤
創作者介紹
創作者 jghs1328 的頭像
jghs1328

jghs1328

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