Problem with strings - Any ideas?

Hey. So, I got an important exam this saturday in programming, and I started doing some preparation exercises for a few weeks. Right now, I got across some String/Hashing exercise which I have no idea how to solve..
The problem is ranked with difficulty 4/5 (which means it's really unlikely I would get anything like it), but I would still like to know what is the idea behind it (ie: how to get started into solving it).

Here is it:
You are given a text formed by N characters (lower or upper case letters and digits). A substring of the text is a sequence of characters which appear on continuous positions in the text.

Task: Given a number K, determine the length of the longest substring which appears in the text at least K times.

Entry data: The file substr.in will contain on the first line the numbers N and K, separated with a space. The second line is a text formed by N characters, without spaces, ending with a newline.

Output data: The file substr.out should contain only one line, having printed the max length of the substring which appears at least K times in the text.

Restrictions:
1 <= N <= 16.384
1 <= K <= N
For 30% of the tests, N <= 1.000

Example:

substr.in
13 3
yabadabadooba


substr.out
2


Explanation: The substring ba appears three times in the text. Any substring of a bigger length (like aba) appears less than three times.


They also say that this problem should use:
Searching: Binary Search
Strings: Suffix Array
Data Structures: Hash

However, I have no idea how to get it started.. Could anyone give me a hint? Or guide me to some good tutorials for this kind of problems? I really need help with this.

Thanks in advance.

Raul
Topic archived. No new replies allowed.