部分文字列検索

我々がソフトウェアエンジニアとして毎日行う1つの一般的なタスクは、入力を解析し、値を検証するための文字列で動作します.
この記事では、与えられた文字列が与えられた部分文字列を含むかどうかを調べる関数を記述します.このプロセスは、通常、部分文字列の検索として知られており、通常はほとんどの言語の組み込み機能ですが、我々は自分自身のための機能を実装するプロセスを理解する!
今日の記事についてはRust 我々の選択言語としてCargo これは錆パッケージマネージャです.
コマンドラインで次のコマンドを実行する必要があります.

mkdir substring_search
cd substring_search
cargo init --name substring_search

これはディレクトリ名substring_search , そのディレクトリに移動し、新しい名前のsubstring_search .

テスト

いつものように、テストを最初に開始することができます!
インsrc/main.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);
    }
}

これを歩いて、我々は宣言を開始するattribute 設定された環境がtest , 私たちは、そのコードをtests モジュールです.
インサイド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.

我々の場合SEARCH_STRING_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 in the near future when we tackle the topic of compound types in Rust.

この定数を使用して、テストケースを実装しました.

検索文字列の先頭にある部分文字列.

検索文字列の中央にある部分文字列.

検索文字列の末尾にある部分文字列.

検索文字列に存在しない部分文字列.

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.

テストを実行するには、次のコマンドラインを実行します.cargo test .

実装

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);
}

この実装のためにcontains 機能が必要String インスタンス

The haystack 我々が中で捜していることneedle

The needle 我々が中で捜しているものhaystack

haystackが針より小さいならば、それは針を含むことができないので、それは帰りますfalse .
haystackの開始から針のサイズまでのhaystacks文字が針に等しいならば、我々は帰りますtrue .
さもなければ、私たちは、haystackの最初の文字を切り離して、針のために検索する新しいhaystackとしてそれを使用します.
成功した部分文字チェックは次のように視覚化できます:

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

失敗した部分文字チェックは次のように視覚化できます:

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

JavaScriptを使用すると、同じ言語で同じ再帰的な機能を実装できます.

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);
}

結論

いくつかの他のアルゴリズムと比較して、我々はこのような、またはこのようなシリーズで見てきた、これは比較的簡単なアルゴリズムです.いくつかの意味では、それは我々が日常的に文字列、部分文字列などを使用して以来、理解するために重要なものですが、そして、大規模には、プレーの基本的なアルゴリズムを当然のために取る.
私はあなたが今日のポストにいくつかの値を見つけ、あなたが質問、コメントや提案がある場合は、ポストの下のコメントエリアにそれらを残して自由に感じてほしい!