3
$\begingroup$

I encountered this problem from game development which I will formulate in a more formal way:

Given a sequence $A = a_1, a_2, \dots, a_m$ and a permutation of $\{1, \dots, n\}$, $B = b_1, b_2, \dots b_n$, find all $i$ such that for all $1 \leq j \leq n$, $a_{i + j}$ is the $b_j$th smallest element of $a_{i + 1}, a_{i + 2}, \dots, a_{i + n}$.

Example:

  • $A = 6, 1, 3, 4, 5$
  • $B = 1, 2, 3$
  • $i = 1$: $1, 3, 4$ matches the relative order of $1, 2, 3$
  • $i = 2$: $3, 4, 5$ matches the relative order of $1, 2, 3$

The brute force approach consists of sorting each subsequence of length $n$ and comparing the sorted indices to $B$, and this is done $m - n + 1$ times, thus resulting in a time complexity of $\mathcal{O}(mn \log n)$.

I have only managed to improve this very slightly, by sorting only the first subsequence in $\mathcal{O}(n \log n)$ time and then removing $a_i$ and inserting $a_{i + n + 1}$ which both take $\mathcal{O}(n)$ time, resulting in a time complexity of $\mathcal{O}(n \log n + mn)$.

I do realise that my approaches are very rudimentary and there should exist a much more efficient algorithm that runs in less than $\mathcal{O}(m n)$ time. Unfortunately, I cannot think of any relevant algorithms that I know of, and searching online with how I described the problem have yet brought any useful resources.

$\endgroup$
  • $\begingroup$ "find all $i$ such that for all $1 \leq j \leq n$, $a_{i + j}$ ", do you mean "find all $i$ such that for all $1 \leq j \leq n-i$, $a_{i + j}$ "? What is that $a_{i + k}$ at the end of the line? $\endgroup$ – Apass.Jack Oct 25 '18 at 22:23
  • $\begingroup$ @Apass.Jack sorry I messed up the indices. Please see the edited version $\endgroup$ – Jingjie YANG Oct 26 '18 at 6:26
  • $\begingroup$ Can you imitate Knuth–Morris–Pratt algorithm and write an answer? That approach should be able to produce an efficient algorithm at least in the case when $m$ is much larger than $n$. $\endgroup$ – Apass.Jack Oct 27 '18 at 13:09
  • $\begingroup$ Boyer–Moore string-search algorithm could be imitated as well. $\endgroup$ – Apass.Jack Oct 27 '18 at 13:19
  • 1
    $\begingroup$ If you prefer, I can write an answer. By the way, are you indeed a "12th-grade student" in France? My answer might depend on your background. $\endgroup$ – Apass.Jack Oct 28 '18 at 21:31

Your Answer

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

Browse other questions tagged or ask your own question.