※ 引述《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