Substring search
Tags: computerscience, algorithms, data, rust
Published: 2022-04-05 21:39:43

One common task we do daily as software engineers is working with strings to parse inputs, validate values and the like.

In this article we will be writing a function to check if a given string contains a given substring. This process is commonly known as a substring search and is usually a built-in feature of most languages but we will implement the functionality for ourselves to understand the process at hand!

For todays article we will be working with [Rust](https://www.rust-lang.org/) as our language of choice and [Cargo](https://doc.rust-lang.org/stable/cargo/) which is the Rust package manager.

To begin we must execute the following in the command line:

```sh
mkdir substring_search
cd substring_search
cargo init --name substring_search
```

This will create a directory called `substring_search`, move into that directory and then initialise a new Rust project via Cargo named `substring_search`.

## Tests

As always, lets begin first with the tests!

In `src/main.rs` we can write the following:

```rs
#[cfg(test)]
mod tests {
    const SEARCH_STRING_SLICE: &'static str = "abcdefg";

    #[test]
    fn returns_true_for_substring_at_start_of_string() {
        let haystack = SEARCH_STRING_SLICE.to_string();
        let needle = String::from("ab");

        assert_eq!(super::contains(haystack, needle), true);
    }

    #[test]
    fn returns_true_for_substring_at_middle_of_string() {
        let haystack = SEARCH_STRING_SLICE.to_string();
        let needle = String::from("d");

        assert_eq!(super::contains(haystack, needle), true);
    }

    #[test]
    fn returns_true_for_substring_at_end_of_string() {
        let haystack = SEARCH_STRING_SLICE.to_string();
        let needle = String::from("fg");

        assert_eq!(super::contains(haystack, needle), true);
    }

    #[test]
    fn returns_false_for_invalid_substring() {
        let haystack = SEARCH_STRING_SLICE.to_string();
        let needle = String::from("hij");

        assert_eq!(super::contains(haystack, needle), false);
    }
}
```

Walking through this, we begin by declaring an [attribute](https://doc.rust-lang.org/rust-by-example/attribute.html) which states that when the configured environment is `test`, we should run the code within the `tests` module.

Inside the `tests` module we declare a constant which is to be the search string used across each of our tests.

> **Sidenote 1:**
>
> Rust has two _kinds_ of string, for want of a better term, these are known as _strings _and _slices_. A _string _is of the `String` type and a _slice _is of the `&str` type.

In the case of our `SEARCH_STRING_SLICE` constant it is declared as a _slice_.

> **Sidenote 2:**
>
> The reason it is declared as a slice initially is because rust cannot compile static `Strings` since strings are mutable but it can compile static `&str` slices but this is a side topic which I will be covering in [my other series on the Rust programming language](https://dev.to/jamesrweb/series/6969) in the near future when we tackle the topic of [compound types in Rust](https://doc.rust-lang.org/book/ch03-02-data-types.html#compound-types).

With this constant defined, we implemented our test cases:

1. A substring that is at the beginning of the search string.
2. A substring that is in the middle of the search string.
3. A substring that is at the end of the search string.
4. A substring that does not exist in the search string.

> **Sidenote 3:**
>
> When we want to run our `contains` function, which we will implement in the next section, we use `super::contains` to call it.
>
> This is because `super` is a module scope keyword which tells rust to look in the parent scope of the module for the function and not in the current `tests` module scope for example.
>
> If we had defined the `contains` function in the `tests` module itself, we would instead use the `self::contains` syntax.

To run the tests we can run the following via the command line: `cargo test`.

## Implementation

```rs
fn contains(haystack: String, needle: String) -> bool {
    if haystack.len() < needle.len() {
        return false;
    }

    if haystack.chars().take(needle.len()).collect::<String>() == needle {
        return true;
    }

    return contains(haystack.chars().skip(1).collect(), needle);
}
```

For this implementation of the `contains` function we require two `String` instances:

1. The `haystack` that we will be searching within for the `needle`
2. The `needle` which we will be searching for within the `haystack`

If the haystack is smaller than the needle, it cannot contain the needle and thus it will return `false`.

If the haystacks characters from the start of the haystack to the size of the needle is equal to the needle then we return `true`.

Otherwise we slice off the first character of the haystack and use that as the new haystack to search within for the needle.

A successful substring check could be visualised like so:

```text
Recursive iteration #1:

haystack = "abc"
needle = "bc"

haystack length < needle length ❌
"ab" is equal to the needle ❌

Recursive iteration #2:

haystack = "bc"
needle = "bc"

haystack length < needle length ❌
"bc" is equal to the needle ✔️

Return true
```

An unsuccessful substring check could be visualised like so:

```text
Recursive iteration #1:

haystack = "abc"
needle = "de"

haystack length < needle length ❌
"ab" is equal to the needle ❌

Recursive iteration #2:

haystack = "bc"
needle = "de"

haystack length < needle length ❌
"bc" is equal to the needle ❌

Recursive iteration #3:

haystack = "c"
needle = "de"

haystack length < needle length ✔️

Return false
```

We can implement the same recursive functionality using any language, for example with JavaScript it is effectively the same code:

```js
function contains(haystack, needle) {
  if(haystack.length < needle.length) {
    return false;
  }

  if(haystack.slice(0, needle.length) == needle) {
    return true;
  }

  return contains(haystack.slice(1), needle);
}
```

## Conclusions

Compared to some of the other algorithms we have looked at in this series such as [generating permutations](https://dev.to/jamesrweb/permutations-4be1) or [approximating PI](https://dev.to/jamesrweb/approximating-pi-4j2o), this is a relatively simple algorithm. In some sense though it is a more important one to understand since we use strings, substrings, etc on a daily basis and, by and large, take for granted the underlying algorithms at play.

I hope that you found some value in todays post and if you have any questions, comments or suggestions, feel free to leave those in the comments area below the post!