1
$\begingroup$

Let's say we have a string $s$. We define a unique substring in $s$ as a substring that occurs only once in $s$. How can we efficiently find such a substring with the smallest length in $s$?
The most obvious solution is in $O(n^3)$ by checking every substring. What if we can preprocess the string?

$\endgroup$
  • $\begingroup$ Nice exercise! What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Jun 18 '17 at 14:58
1
$\begingroup$

You can try suffix array approach which find all suffix of a given string of length n in O(n) time. There are many algorithm to construct suffix array from a given input string.
Look at complete taxonomy here
http://www.cas.mcmaster.ca/~bill/best/algorithms/07Taxonomy.pdf

For your problem you can use suffix array couple with some additional counter to find solution.

$\endgroup$
1
$\begingroup$

I can suggest a simple method that will achieve this in many practical cases in linear time, for example if you examine "War and Peace", but will fail if some characters are very common.

Assume the string to be examined has n ≥ 1 characters, and there are m characters where m is not very large. Build a table which contains for every character c all positions within the string where that character c can be found. If we are lucky, some character appears only once and we have a solution. Then for each character c, and each second character d, find all locations where the string "cd" can be found - we do this preferably first for characters c that are rare. Again we might be lucky and find a two letter string occurring only once. We repeat for three, four, five character strings and so on.

If we have n characters, then the table of substrings can only have about n/2 entries (otherwise some substring must be unique). With "War and Peace" this will work quite quickly. You might add some code for the situation where the number of different substrings is very small, for example with the string "ababababab...".

I think this might run in n log n in many practical cases (the length of the shortest unique substring might grow with log n) and in quadratic time worst case with a good implementation.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.