how to solve this problem?
construct suffix tree for N times and then LCP or there is easier and faster way?

Construct suffix tree for each window. Sliding should be at most O(k).

Try DP.
It's easier to code (+ short) and run much faster than using suffix tree although having the same complexity O(N*K).

Could you please decribe me DP solution?

Stupid implementation of the hash-table is even easier to code and much easier to invent.

Coding is not difficult at all. It seems to be more interesting that there exists O(n + k) solution, isn't it?

O(n=4000 + k=1000) would work 0.001ms ;)

Hardly. O(n + k) may have arbitrary coefficient. And no one said that solution had been submitted at Timus.

AC in 0.109 using only Z-function (also called suffix-function)

Z-function is not necessary here, KMP is enough.
0.14 using KMP.

And what is the "stupid implementation of the hash-table"?
My stupid implementation got TL.

Could you explain how to use KMP here?

Read this:
http://e-maxx.ru/algo/prefix_function

Edited by author 22.02.2014 15:24

Probably DP solution is actually a suffix automation.
In suffix automation,  we have the following DP.
Let X is some state of DAWG.
Let DP[X] =1+sum(DP[Y]){there is an edge from X to Y in DAWG}.
Then the answer is DP [ROOT] - 1. (Because empty substring not counts)

Edited by author 12.07.2017 12:20