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:

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*

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
substr.out
Explanation: The substring appears three times in the text. Any substring of a bigger length (like ba) appears less than three times.aba |

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.

Topic archived. No new replies allowed.