Last week, there was a preliminary ICPC contest in Korea, whose result is used to select teams from various universities to advance to the Seoul Regional (regional contest in Korea)

This is the problemset: http://icpckorea.org/2018/preliminary/problems.pdf

Most problems were solved, at least algorithmically, by people during the contest or after the contest. However, anyone, including some top-tier people in our country, couldn't solve **problem C**.

In the contest, problem C was solved, but it was just because the test data was super weak to allow solutions with complexity *O*(*n*^{2} / *k*) :p Since the description is short enough, I will not describe the problem here, just click the link to see the task.

I am really curious about the solution of this problem. Could I get some hints or entire solutions for this task? Thanks in advance :)

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 :)

Ask the legends > @Petr @tourist

When

kis 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 lengthL(maybe except the last one). For example, whenL= 3, we will divide the stringababbabbabalike this:aba|bba|bba|baFor each two neighboring part we compute the LCP(longest common prefix) and the LCS(longest common suffix) of them. Every substring of length 2

Lwill 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) whenj-i≤k. And we'll get something like "substrings starts with [l,r] is not ak-LS": there are of them: with them we can find the number ofk-LSsubstrings with lengthkLusing sweep line. The total complexity isWhen , we'll use the second algorithm, otherwise we'll use the first algorithm. The total complexity is .

Sorry for my poor English.

Wow, this is an wonderful solution. I'm impressed by the idea using LCP and LCS to check the sameness. Thank you very much!

The same idea was used in CNOI2016.

link