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 withRust as our language of choice andCargo which is the Rust package manager.

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

mkdirsubstring_searchcdsubstring_searchcargo init--name substring_search

This will create a directory calledsubstring_search, move into that directory and then initialise a new Rust project via Cargo namedsubstring_search.

Tests

As always, lets begin first with the tests!

Insrc/main.rs we can write the following:

#[cfg(test)]modtests{constSEARCH_STRING_SLICE:&'staticstr="abcdefg";#[test]fnreturns_true_for_substring_at_start_of_string(){lethaystack=SEARCH_STRING_SLICE.to_string();letneedle=String::from("ab");assert_eq!(super::contains(haystack,needle),true);}#[test]fnreturns_true_for_substring_at_middle_of_string(){lethaystack=SEARCH_STRING_SLICE.to_string();letneedle=String::from("d");assert_eq!(super::contains(haystack,needle),true);}#[test]fnreturns_true_for_substring_at_end_of_string(){lethaystack=SEARCH_STRING_SLICE.to_string();letneedle=String::from("fg");assert_eq!(super::contains(haystack,needle),true);}#[test]fnreturns_false_for_invalid_substring(){lethaystack=SEARCH_STRING_SLICE.to_string();letneedle=String::from("hij");assert_eq!(super::contains(haystack,needle),false);}}

Walking through this, we begin by declaring anattribute which states that when the configured environment istest, we should run the code within thetests module.

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

Sidenote 1:

Rust has twokinds of string, for want of a better term, these are known asstrings _and _slices. A _string _is of theString type and a _slice _is of the&str type.

In the case of ourSEARCH_STRING_SLICE constant it is declared as aslice.

Sidenote 2:

The reason it is declared as a slice initially is because rust cannot compile staticStrings since strings are mutable but it can compile static&str slices but this is a side topic which I will be covering inmy other series on the Rust programming language in the near future when we tackle the topic ofcompound types in Rust.

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 ourcontains function, which we will implement in the next section, we usesuper::contains to call it.

This is becausesuper is a module scope keyword which tells rust to look in the parent scope of the module for the function and not in the currenttests module scope for example.

If we had defined thecontains function in thetests module itself, we would instead use theself::contains syntax.

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

Implementation

fncontains(haystack:String,needle:String)->bool{ifhaystack.len()<needle.len(){returnfalse;}ifhaystack.chars().take(needle.len()).collect::<String>()==needle{returntrue;}returncontains(haystack.chars().skip(1).collect(),needle);}

For this implementation of thecontains function we require twoString instances:

1. Thehaystack that we will be searching within for theneedle
2. Theneedle which we will be searching for within thehaystack

If the haystack is smaller than the needle, it cannot contain the needle and thus it will returnfalse.

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

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:

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:

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:

functioncontains(haystack,needle){if(haystack.length<needle.length){returnfalse;}if(haystack.slice(0,needle.length)==needle){returntrue;}returncontains(haystack.slice(1),needle);}

Conclusions

Compared to some of the other algorithms we have looked at in this series such asgenerating permutations orapproximating PI, 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!