The problem is called substring search or string search or string matching. It's called a substring even if the elements of the array aren't characters. In this answer, I'll use character to refer to elements of the arrays, but this can be any kind of data (numbers, nested data structures, …). The standard terminology is:
- subset (without multiplicity): all the elements of $A$ are also found in $B$. For example $(1,2,3,1)$ is a subset of $(3,4,1,2)$.
- subset with multiplicity: for every element of $A$, there is a corresponding element in $B$. The difference from the basic subset problem is that if an element in $A$ is repeated, it must be repeated at least as many times in $B$. For example $(1,2,3,1)$ is a subset of $(3,4,1,1,2)$ but not of $(3,4,1,2)$. The terminology around this problem isn't completely standardized, sometimes ”subset“ refers to this.
- subsequence: the elements of $A$ are also present in $B$, in the same order, but there may be other elements in between. For example $(1,2,3)$ is a subsequence of $(0,1,0,2,3,4)$ and $(1,2,2,3)$ but not of $(3,1,2,0)$.
- substring: the elements of $A$ are also present in $B$, in the same order and consecutively. For example $(1,2,3)$ is a substring of $(0,1,2,3,4)$ but not of $(1,2,2,3)$.
Substring search is a very well-studied problem. The naive approach, where you take each possible starting position in $B$ in turn and try to match $A$ there, runs in $O(m\,n)$ where $m$ is the length of $A$ and $n$ is the length of $B$.
The naive approach can be improved because it often ends up making tests which could have been known to be false or whose outcome doesn't affect the final result. For example:
- If one of the elements of $A$ never occurs in $B$, this can be noticed with a single pass in $B$, in time $O(n)$: there's no need to test the other characters of $A$. More generally, if a character in $A$ occurs rarely in $B$, it's best to match this one first against the elements of $B$.
- When matching
abcdabe at the start of abcdefabcdabcdabe, once position $5$ is reached (a ≠ e), the naive algorithm tries to match $A$ starting at position $2$. An improvement is to notice that the first character of $A$ wasn't present in the positions of $B$ that have already been read, so there's no need to test $A$ again against earlier positions.
Improved substring search algorithms rely on preprocessing $A$ to notice opportunities like these to make the matching more efficient. For example, a simple approach from a theoretical perspective is to build a deterministic finite automaton that recognizes the regular expression $\mathord{.}^*A$, which recognizes all strings that end in $A$. If the automaton ever reaches an accepting state, this indicates that $A$ has been found as a substring of $B$. This algorithm requires a preprocessing phase on $A$ which requires $O(m^2)$ time; after this, $B$ can be processed with no backtracking. Each position in $B$ requires $O(1)$ time to analyze the character in $B$ and look it up in the table of transitions from the current node in the automaton. Thus the running time for the search (including preprocessing) is $O(m^2 + n)$.
Two common substring algorithms are:
- Knuth-Morris-Pratt, which builds on the same idea as the finite automaton, but constructs a more specialized table in time $O(m)$, for a total running time of $O(n)$.
- Boyer-Moore, which also builds a table, and tries matching from the end of $A$, which allows it to skip characters in $B$. The basic Boyer-Moore algorithm has a $\Theta(m\,n)$ worst case (like naive search), but can pass over non-matching strings in time $n/m$ in the best case. There are Boyer-Moore variants with an $O(m+n)$ worst case.
Intuitively, $O(m+n)$ is as good as it gets, since in the worst case all characters in $m$ and $n$ must be read (the worst case being reached when $B$ is full of substrings that are close to $A$ but not identical).
