# Matching relative order in subsequence of fixed length

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.

• "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? – John L. Oct 25 '18 at 22:23
• @Apass.Jack sorry I messed up the indices. Please see the edited version – Jingjie YANG Oct 26 '18 at 6:26
• 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$. – John L. Oct 27 '18 at 13:09
• Boyer–Moore string-search algorithm could be imitated as well. – John L. Oct 27 '18 at 13:19
• 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. – John L. Oct 28 '18 at 21:31