Ggthjy

Summary: a bunch of algorithms to find if particular substring exists in the string. Meanwhile there's a lot to learn and I am looking forward to implementing more complex ones, I suppose there's some crucial insight regarding style, syntax, or design, which I might be missing. I have also managed to implement the auxiliary functions which potentially would assist me in the future.

Note: the question I have is how to avoid the boilerplate part in the main function. There should have been a some kind of "framework", which would accept the vector of functions and perform the tests. However, for me it's not quite clear how the architecture should be designed.

#include <algorithm>

#include <cassert>

#include <functional>

#include <iostream>

#include <random>

#include <string_view>

#include <utility>

#include <vector>



template <typename T>

std::ostream &operator<<(std::ostream &o, std::vector<T> const &vector)

{ for (auto const &element: vector) o << element << " "; return o; }



namespace string_generator_utility {



    std::string generate_string(std::string::size_type length,

                                std::vector<char>&& alphabet = {'a', 'b', 'c', 'd'}) {

        std::string result;

        static std::random_device rd;

        static std::mt19937_64 mersenne_twister_generator {rd ()};

        const auto supremum = alphabet.size() - 1;

        std::uniform_int_distribution<std::size_t> range {0, supremum};

        for (std::size_t index = 0; index < length; ++index) {

            const auto letter = range(mersenne_twister_generator);

            result += alphabet[letter];

        }

        return result;

    }



    std::vector<std::string> generate_n_strings(std::size_t vector_size, std::size_t string_length,

                                                std::vector<char>&& alphabet = {'a', 'b', 'c', 'd'}) {

        std::vector<std::string> generated;

        generated.reserve(vector_size);

        std::generate_n(std::back_inserter(generated), vector_size,

                        [&]() { return generate_string(string_length, std::move(alphabet)); });

        return generated;

    }



} // namespace string_generator_utility



namespace algo {



  std::vector<std::int64_t> naive_substring(std::string_view haystack, std::string_view needle) {



    const auto haystack_size = haystack.size();

    const auto needle_size = needle.size();

    assert(haystack_size >= needle_size);



    std::vector<std::int64_t> result;

    for (std::size_t index = 0; index < haystack_size - needle_size + 1; ++index) {

        std::size_t offset = 0;

        for (; offset < needle_size; ++offset) {

            if (haystack[index + offset] != needle[offset])

                break;

        }

        if (offset == needle_size) 

            result.push_back(index);

    }

    return result;

  }



  std::vector<std::int64_t> rabin_karp_hash(std::string_view haystack, std::string_view needle) {



    const auto haystack_size = haystack.size();

    const auto needle_size = needle.size();

    assert(haystack_size >= needle_size);



    std::vector<std::int64_t> matches;

    static const auto hash_function = [](std::string_view::iterator begin, std::string_view::iterator end) {

        std::int64_t hash = 5381;

        for (; begin != end; ++begin)

            hash = ((hash << 5) + hash) + *begin;

        return hash;

    };



    const auto needle_hashed = hash_function(std::begin(needle), std::end(needle));

    for (std::size_t index = 0; index < haystack_size - needle_size + 1; ++index) {

        const auto substring_hash = hash_function

        (

            std::begin(haystack) + index, std::begin(haystack) + index + needle_size

        );

        if (substring_hash == needle_hashed) 

            matches.push_back(index);

    }

    return matches;

  }

} // namespace algo



int main() {

  auto vector = string_generator_utility::generate_n_strings(25, 50);

  std::cout << "naive substring:n";

  for (std::size_t index = 0; index < vector.size(); ++index)

  {

      std::cout << vector[index] << ": ";

      auto shift = algo::naive_substring(vector[index], "ab");

      std::cout << shift << "n";

  }

  std::cout << "rabin-karp-substring:n";

  for (std::size_t index = 0; index < vector.size(); ++index)

  {

      std::cout << vector[index] << ": ";

      auto shift = algo::rabin_karp_hash(vector[index], "ab");

      std::cout << shift << "n";

  }

  return 0;

}

From a readability viewpoint, your operator<< for std::vector declared at the top of your file should be spread out onto multiple lines so that it is easier to read and understand.

Also, the calculation of ((hash << 5) + hash) should be rewritten as the simpler hash * 33. The compiler will know the best way to multiply a number by 33. This could be a multiply, a shift-and-add like you've coded, or some sequence involving the address calculation instructions.

Rather than using an assert to verify that the needle is not longer than the haystack (which will only check the condition if the NDEBUG macro is not defined), just check the condition and return an empty collection.

In rabin_karp_hash you assume that two strings match if their hash values are the same. This is not necessarily the case. It is possible, however unlikely, that two different strings will have the same hash value. This is a hash collision. To ensure that your potential match are identical strings, you still need to compare both strings when the hashes match.

To simplify the code in main and eliminate the duplication, you can create a class with a virtual compare member. Then derive two classes from it, one for the naive comparison, the other for the Rabin-Karp one. Put your loop into another function, and pass instances of the appropriate derived class to use the specific comparison you want to test.

1. I think the assertion in the rabin_karp_hash is redundant. There is nothing wrong with trying to find a substring with a size exceeding that of a text (although the result is self-evident), besides you can just return an empty vector there.



2. 
   

   I'd replace

   
   
   

   for (; offset < needle_size; ++offset) {
   
       if (haystack[index + offset] != needle[offset])
   
           break;
   
   }
   
   

   
   
   

   with something like

   
   
   

   while (offset < needle_size && haystack[index + offset] == needle[offset])
   
       ++offset;