Hi. I'm attempting to solve this problem: http://main.edu.pl/en/archive/pa/2011/naj (it belongs to the competition 'Algorithmic Engagements 2011')

Summary: Given a long string find the length of the shortest period of the resulting string after removing a single character (A string t is a period of s iff s is a preffix of t^k for some k)

I can't see a way faster than O(N^2) (based on KMP). Could you give me a hint for a faster solution ?

Regards.

Given a sequence of N non-negative integers a[1..N], and two indices (l, r) then f(l, r) is the number of elements in a[l..r] whose frequency in [l, r] is 1.

How would you find the maximum value of this function (faster than O(N²)), ie. compute max(f(l, r)) for all l ≤ r ?

Example. If a[] = { 1, 1, 2, 5, 6, 5, 4, 3 }, then some values of f are f(1, 3) = 1 (2 is the only number in a[1..3] that appears just once), f(3, 5) = 3, f(4, 6) = 1, f(1, 8) = 4. In this particular case the maximum value that f may achieve is 4.

Regards.

Hello. Could anybody provide me with a hint to solve this problem http://main.edu.pl/en/archive/oi/17/cho ? The problem gives you a set of N strings and then asks for the shortest string that has at least M occurrences of the strings. I'm unable to see a correct approach.

Thanks in advance.