Repository: TheAlgorithms/C-Plus-Plus
File: strings/knuth_morris_pratt.cpp (C++)

Code before:
/**
 * @file
 * @brief The [Knuth-Morris-Pratt
 * Algorithm](https://en.wikipedia.org/wiki/Knuth–Morris–Pratt_algorithm) for
 * finding a pattern within a piece of text with complexity O(n + m)
 * @details
 * 1. Preprocess pattern to identify any suffixes that are identical to
 * prefixes. This tells us where to continue from if we get a mismatch between a
 * character in our pattern and the text.
 * 2. Step through the text one character at a time and compare it to a
 * character in the pattern updating our location within the pattern if
 * necessary
 */

#include <iostream>
#ifdef _MSC_VER
#include <string>  // use this for MS Visual C++
#else
#include <cstring>
#endif
#include <cassert>
#include <vector>

/**
 * @namespace string_search
 * @brief String search algorithms
 */
namespace string_search {
/**
 * @brief Generate the partial match table aka failure function for a pattern to
 * search.
 * @param pattern text for which to create the partial match table
 * @returns the partial match table as a vector array
 */
std::vector<size_t> getFailureArray(const std::string &pattern) {
    size_t pattern_length = pattern.size();
    std::vector<size_t> failure(pattern_length + 1);
    failure[0] = std::string::npos;
    size_t j = std::string::npos;
    for (int i = 0; i < pattern_length; i++) {
        while (j != std::string::npos && pattern[j] != pattern[i]) {
            j = failure[j];
        }
        failure[i + 1] = ++j;
    }
    return failure;

Review comment (suggestion):
Since I can't merge if I am the last one to push a change could you document this include?

```suggestion
#include <cassert> /// for assert()
```


Code after:
/**
 * @file
 * @brief The [Knuth-Morris-Pratt
 * Algorithm](https://en.wikipedia.org/wiki/Knuth–Morris–Pratt_algorithm) for
 * finding a pattern within a piece of text with complexity O(n + m)
 * @details
 * 1. Preprocess pattern to identify any suffixes that are identical to
 * prefixes. This tells us where to continue from if we get a mismatch between a
 * character in our pattern and the text.
 * 2. Step through the text one character at a time and compare it to a
 * character in the pattern updating our location within the pattern if
 * necessary
 * @author [Yancey](https://github.com/Yancey2023)
 */

#include <cassert>   /// for assert
#include <iostream>  /// for IO operations
#include <string>    /// for std::string
#include <vector>    /// for std::vector

/**
 * @namespace string_search
 * @brief String search algorithms
 */
namespace string_search {
/**
 * @brief Generate the partial match table aka failure function for a pattern to
 * search.
 * @param pattern text for which to create the partial match table
 * @returns the partial match table as a vector array
 */
std::vector<size_t> getFailureArray(const std::string &pattern) {
    size_t pattern_length = pattern.size();
    std::vector<size_t> failure(pattern_length + 1);
    failure[0] = std::string::npos;
    size_t j = std::string::npos;
    for (int i = 0; i < pattern_length; i++) {
        while (j != std::string::npos && pattern[j] != pattern[i]) {
            j = failure[j];
        }
        failure[i + 1] = ++j;
    }
    return failure;
}

/**