※ 引述《Leon (Achilles)》之銘言：
: 嗯, 剛剛想了一下.
: 這個題目, 是 KMP 的變形.
:
: 難的地方在於, 你怎麼想到正確的方向
: (聽起來有點廢話, 哈哈..)
:
: 這裡我採用之前的定義.
:
: For a sentance, we are given the occurance index.
: Take above example, say, only 3 words {a, b, c}.
: The sentance is [b b a c b a].
:
: The the occurance index will be
: a = {3, 6}.
: b = {1, 2, 5}.
: c = {4 }.
:
:
: 在開始之前, 我們先看幾個非常簡單的作法.
:
: 1. Naive: Arbitary choose 2 position from [1, N],
: then check the condition.
:
: 2. Choose one position as the left boundary, then,
: use the max-min of the rest set the decide the right boundary.
:
: For example, if I choose 2 as my left boundary,
: then I need to choose the right boundary by the max of
: d(2,3) and d(2,4) which cover set {a} and set {c}
:
: The result window is [2, 4].
:
: And the complexity should be O(N* K).
:
: 接下來, 就是有趣的地方了.
:
: 3. Follow the previous algorithm, inspired by KMP.
: When we start from 3, actually we don't need to compare all K groups.
:
: Because from previous step, we know [2] covers {b} for sure.
: And [3,4] covers {a,c} for sure.
:
: In this case, we only need to check the condition for set {b} !
: which is d(3,5).
:
: Then the computational complexity is O(N).
: I'll leave the detail for you.
:
:
:
:

Since you claimed that the complexity is O(N), the innerloop must be amortized O(1), that's why I was wonderingwhat kind of data structure are you maintaining throughout the loop to keep the lookup o(log K). (Small-o, notbig-O.)

it's not me to claim O(lg K).. please check my articleand, my article do explain how to achieve O(1) in innerloop based on KMP concept..

o(lg K) is different than O(lg K)you did claim o(lg K)

我想 leon 的意思是這樣 http://ideone.com/p6STMv