0
$\begingroup$

Given two sequences $A$ and $B$, we want to check if $A$ is a subsequence of $B$ where the elements of $A$ appear in $B$ consecutively and in the same order.

Example 1.

  • input: $A = (4 , 6 , -5), B = (2 , 4 , 6 , -5 , 4)$,
  • output: Yes

Example 2.

  • input: $A = (2 , 6 , 4), B = (2 , 4 , 6 , -5 , 3)$,
  • output: No — although $B$ contains all the elements in $A$, the order is not correct.

Example 3.

  • input: $A = (2 , 6 , 4), B = (2 , 3 , 6 , -5 , 4)$,
  • output: No — although $B$ contains all the elements of $A$ in the correct order, they are not consecutive.

Let $n$ and $m$ be the size of $A$ and $B$.

How fast can we solve this problem?

What I have tried

I have an algorithm that runs in time $O(nm)$ as follows:

go over elements of A, for each of them go over elements of B and see if we can find a matching element, which is after the matching element for the previous element of A.

$\endgroup$
  • 2
    $\begingroup$ @D.W. someone edited my question till what i have tried , my research , my thoughts all have disappered $\endgroup$ – Computernerd Aug 2 '14 at 3:36
  • 2
    $\begingroup$ I understand, and I saw the edit, but: 1. If you were asking us to check your algorithm, that is off-topic for this site (hence the edit). 2. If you are asking us whether one can find an algorithm that is faster than $O(mn)$ time, then we'd like to see what you've tried, what research you've done, your attempts, etc. The original version did not describe what you have tried towards finding an algorithm faster than $O(mn)$, your thoughts about how to accomplish that, or what research you've done. $\endgroup$ – D.W. Aug 2 '14 at 3:49
  • 1
    $\begingroup$ You need string searching algorithms en.wikipedia.org/wiki/String_searching_algorithm $\endgroup$ – Lurr Aug 3 '14 at 23:50
  • 1
    $\begingroup$ Are you looking for a substring (the elements of A need to be found consecutively in B) subsequence (the elements don't need to be consecutive)? Your text seems to describe a subsequence, but in your example 2, $A$ is a subsequence of $B$, yet the answer is no. $\endgroup$ – Gilles 'SO- stop being evil' Aug 3 '14 at 23:52
  • 1
    $\begingroup$ @Computernerd In a subsequence, the elements aren't necessarily consecutive. $A = (B_0, B_2, B_4)$ is a subsequence of $B$. So you're looking for a substring after all. $\endgroup$ – Gilles 'SO- stop being evil' Aug 5 '14 at 9:01
5
$\begingroup$

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 (ae), 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).

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

The problem can be solved in time $O(m+n)$ (check the algorithm for longest common subsequence).

We have to read all elements of $A$ and $B$ in the worst case, so it cannot be solved faster than $\Omega(m+n)$.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ You transformed a "check my solution" question into a "problem dump" -- that's no improvement. Asking the OP to improve their question, e.g. by adding a specific, reasonably focused question about their attempt, would have been better, at least as a first step. $\endgroup$ – Raphael Aug 1 '14 at 22:17
  • 1
    $\begingroup$ -1 for not giving at least a link to the algorithm. Also note that your edit appears to have changed the problem specification from non-continuous subsequence to continuous in addition to changing the question asked. $\endgroup$ – FrankW Aug 1 '14 at 22:20
  • 2
    $\begingroup$ @FrankW, I think it is easy to find the algorithm by Googling the name of the problem, this is not Stack Overflow, if you prefer to give the detailed algorithm you can do so. I think it is common here to just give the hint. Also subsequence does not need to be continuous, the term for continuous subsequence is substring. ps: I find down-voting an answer question which is correct not constructive and unusual. $\endgroup$ – Kaveh Aug 1 '14 at 22:32
  • 1
    $\begingroup$ @Kaveh, a problem dump is where the poster provides just a problem statement/specification (often it is something that would make a standard exercise in an undergraduate-level course) without showing much evidence of effort or progress on their part, and without formulating a more specific question. See, e.g., meta.cs.stackexchange.com/a/751/755 and the links there, and meta.cs.stackexchange.com/a/839/755, and everything tagged homework on meta. $\endgroup$ – D.W. Aug 1 '14 at 23:31
  • 1
    $\begingroup$ Thanks D.W. @Raphael, and my point is you can edit the question to fix whatever issue you have with my edit. If you feel the question should also contain what OP did just add it back in place of complaining about my edit. $\endgroup$ – Kaveh Aug 2 '14 at 12:05

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.