The problem of exact shortest unique substring (SUS) is formulated as follows:

Given a string S and a position p in S, find a substring of S that (1) is unique in S, (2) covers p, and (3) there is no shorter substring of S, which satisfies (1) and (2).

For instance, for S = aabccabbcb and p = 3, there are three shortest unique substrings of S covering p: aab, abc, and bcc.

The problem originally has been studied in the work of Pei and colleagues [1]. It has been motivated by its applicability in locating the shortest unique snippets of the query string in a long string. Computation of exact SUSs found applications also in event analysis and bioinformatics.

The algorithm proposed in [1] computes all exact SUSs in quadratic time and linear space with respect to the length of string S. Later, there were several improvements, including using linear time and space to construct a data structure that allows any further exact SUS query to be answered in constant time.

In this paper, the authors consider an approximate version of the problem, where a fixed number of mismatches is allowed. A generic in-place algorithmic framework is proposed to solve both exact and approximate k-mismatch (k ≥ 1) SUS problems. For a string of length n, the framework uses 2n words, each of ⌈log₂n⌉ bits, plus n bytes. Using the framework, it is possible to solve the exact SUS problem in linear time, and the approximate k-mismatch SUS problem in quadratic time for any k. The reported results of experiments show that the proposed framework is competitive with respect to both space consumption and speed.

The paper is quite technical, describing details of four different algorithms. The authors do a good job of explaining them and provide the high-level picture. However, readers would profit from more elaborate examples.