<p>You are asking about "quasiperiodicity".   This is a well-studied topic and a google scholar search will turn up many papers about it.  For example, there is an <span class="math-container">$O(n (\log n)^2)$</span> algorithm
<a href="https://www.sciencedirect.com/science/article/pii/030439759390159Q" rel="nofollow noreferrer">here</a> and an <span class="math-container">$O(n \log n)$</span> algorithm <a href="https://link.springer.com/chapter/10.1007/3-540-45123-4_33" rel="nofollow noreferrer">here</a>.</p>

CC BY-SA 4.0
2018-11-30T15:38:17.280Z
I just noticed the OP has cross-posted on this site as well after I posted [my answer here](https://cs.stackexchange.com/questions/100756/find-shortest-prefix-to-generate-original-string-by-overlapping/100764#100764). Since OP is only interested in the shortest substring (which coincides with the prefix of $S$ of length equal to the quasiperiodicity) that covers $S$ there exists an $O(n)$ algorithm.
orlp
CC BY-SA 4.0
2018-11-30T11:19:01.200Z
2018-11-30T11:19:01.200Z
Jeffrey Shallit
<p>Given a string <span class="math-container">$S$</span>, I want to find the prefix string <span class="math-container">$P$</span> of shortest length, such that the original string <span class="math-container">$S$</span> can be generated by concatenating copies of <span class="math-container">$P$</span> (where overlapping is allowed).</p>

<p>For example, if <span class="math-container">$S = atgatgatatgat$</span>, I want to find <span class="math-container">$P = atgat$</span>; <span class="math-container">$P$</span> is the smallest prefix of <span class="math-container">$S$</span> that can be concatenated (in this case three times, starting at indices <span class="math-container">$\{0,3,8\}$</span> of <span class="math-container">$S$</span>, where the first and second copies overlap but the second and third copies do not overlap) to equal <span class="math-container">$S$</span>.</p>

<p>Obviously, there is an <span class="math-container">$\mathcal{O}(n^2)$</span> algorithm by checking each prefix of <span class="math-container">$S$</span>, but a colleague mentioned it might be possible to do it in <span class="math-container">$\mathcal{O}(n \log n)$</span>. I'm thinking of using suffix arrays for different prefixes of <span class="math-container">$S$</span> but haven't quite been able to proceed from there.</p>

<ds.algorithms><string-matching><string-search>
Find shortest prefix to generate original string by overlapping
Robert Lee
# Find shortest prefix to generate original string by overlapping

(Asked by: username_0 on 2018-11-30)

Given a string $S$, I want to find the prefix string $P$ of shortest length, such that the original string $S$ can be generated by concatenating copies of $P$ (where overlapping is allowed).

For example, if $S = atgatgatatgat$, I want to find $P = atgat$; $P$ is the smallest prefix of $S$ that can be concatenated (in this case three times, starting at indices $\{0,3,8\}$ of $S$, where the first and second copies overlap but the second and third copies do not overlap) to equal $S$.

Obviously, there is an $\mathcal{O}(n^2)$ algorithm by checking each prefix of $S$, but a colleague mentioned it might be possible to do it in $\mathcal{O}(n \log n)$. I'm thinking of using suffix arrays for different prefixes of $S$ but haven't quite been able to proceed from there.

**Tags:** ds.algorithms, string-matching, string-search

---

## 1 answers

### Answer by username_1 on 2018-11-30. Score: 2

You are asking about "quasiperiodicity". This is a well-studied topic and a google scholar search will turn up many papers about it. For example, there is an $O(n (\log n)^2)$ algorithm
[here](https://www.sciencedirect.com/science/article/pii/030439759390159Q) and an $O(n \log n)$ algorithm [here](https://link.springer.com/chapter/10.1007/3-540-45123-4_33).

> **Comments:**
> **username_2**: I just noticed the OP has cross-posted on this site as well after I posted [my answer here](https://cs.stackexchange.com/questions/100756/find-shortest-prefix-to-generate-original-string-by-overlapping/100764#100764). Since OP is only interested in the shortest substring (which coincides with the prefix of $S$ of length equal to the quasiperiodicity) that covers $S$ there exists an $O(n)$ algorithm.  

---

