하위 문자열 검색

소프트웨어 엔지니어로서 매일 수행하는 일반적인 작업 중 하나는 문자열을 사용하여 입력을 구문 분석하고 값을 확인하는 등의 작업을 수행하는 것입니다.

이 기사에서는 주어진 문자열에 주어진 하위 문자열이 포함되어 있는지 확인하는 함수를 작성할 것입니다. 이 프로세스는 일반적으로 하위 문자열 검색으로 알려져 있으며 일반적으로 대부분의 언어에 내장된 기능이지만 당면한 프로세스를 이해하기 위해 기능을 구현합니다!

오늘 기사에서는 선택한 언어로 Rust과 Rust 패키지 관리자인 Cargo을 사용하여 작업할 것입니다.

시작하려면 명령줄에서 다음을 실행해야 합니다.

mkdir substring_search
cd substring_search
cargo init --name substring_search

그러면 substring_search 라는 디렉토리가 생성되고 해당 디렉토리로 이동한 다음 Cargo를 통해 substring_search 라는 새 Rust 프로젝트가 초기화됩니다.

테스트

항상 그렇듯이 먼저 테스트부터 시작하겠습니다!
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);
    }
}

이를 살펴보면서 구성된 환경이 test 일 때 tests 모듈 내에서 코드를 실행해야 함을 나타내는 attribute을 선언하는 것으로 시작합니다.
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 인스턴스가 필요합니다.

haystack 내에서 검색할 needle

needle 내에서 검색할 haystack

건초 더미가 바늘보다 작은 경우 바늘을 담을 수 없으므로 반환됩니다false .

건초 더미 시작부터 바늘 크기까지의 건초 더미 문자가 바늘과 같으면 true 를 반환합니다.

그렇지 않으면 우리는 건초더미의 첫 번째 문자를 잘라내어 새로운 건초더미로 사용하여 바늘 내에서 검색합니다.

성공적인 하위 문자열 검사는 다음과 같이 시각화할 수 있습니다.

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

결론

또는 와 같이 이 시리즈에서 살펴본 다른 일부 알고리즘과 비교할 때 이것은 상대적으로 간단한 알고리즘입니다. 어떤 의미에서는 문자열, 하위 문자열 등을 매일 사용하고 대체로 기본 알고리즘을 당연하게 여기기 때문에 이해하는 것이 더 중요합니다.

오늘 게시물에서 가치를 발견하셨기를 바라며 질문, 의견 또는 제안 사항이 있으면 게시물 아래의 댓글 영역에 자유롭게 남겨주세요!