I thought quite a long time with my previous teammates, but I couldn't figure out anything :(

I also searched for some papers, but I could only find the case where K = 2.

Can someone solve this problem? This seems to be quite interesting problem, and I would be pleased if I could know the solution :)

When k is large, it's easy to solve the problem with complexity .

When k = 2, let's count how many substrings are in the form of "AA". This is a classic problem: assume that the length is 2L , divide the string into several parts, where each part has a length L (maybe except the last one). For example, when L = 3, we will divide the string ababbabbaba like this:

aba|bba|bba|ba

For each two neighboring part we compute the LCP(longest common prefix) and the LCS(longest common suffix) of them. Every substring of length 2L will cover at most three parts, with LCP and LCS we can easily compute the answer.

Let's back to the original problem. We don't compute LCP and LCS of all neighboring parts; Just compute all parts i, j(i < j) when j - i ≤ k . And we'll get something like "substrings starts with [l, r] is not a k-LS": there are of them: with them we can find the number of k - LS substrings with length kL using sweep line. The total complexity is

When , we'll use the second algorithm, otherwise we'll use the first algorithm. The total complexity is .

Sorry for my poor English.