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

Code before:
 * @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;
}

/**
 * @brief KMP algorithm to find a pattern in a text
 * @param pattern string pattern to search
 * @param text text in which to search
 * @returns the starting index of the pattern if found
 * @returns `std::string::npos` if not found
 */
size_t kmp(const std::string &pattern, const std::string &text) {
    if (pattern.empty()) {
        return 0;
    }
    std::vector<size_t> failure = getFailureArray(pattern);
    size_t text_length = text.size();
    size_t pattern_length = pattern.size();
    size_t k = 0;
    for (size_t j = 0; j < text_length; j++) {
        while (k != std::string::npos && pattern[k] != text[j]) {
            k = failure[k];
        }
        if (++k == pattern_length) {
            return j - k + 1;
        }
    }
    return std::string::npos;
}
}  // namespace string_search

using string_search::kmp;

/**
 * @brief self-test implementations
 * @returns void

Review comment (suggestion):
Shouldn't this be npos now?

```suggestion
        return std::string::npos;
```


Code after:
 * @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;
}

/**
 * @brief KMP algorithm to find a pattern in a text
 * @param pattern string pattern to search
 * @param text text in which to search
 * @returns the starting index of the pattern if found
 * @returns `std::string::npos` if not found
 */
size_t kmp(const std::string &pattern, const std::string &text) {
    if (pattern.empty()) {
        return 0;
    }
    std::vector<size_t> failure = getFailureArray(pattern);
    size_t text_length = text.size();
    size_t pattern_length = pattern.size();
    size_t k = 0;
    for (size_t j = 0; j < text_length; j++) {
        while (k != std::string::npos && pattern[k] != text[j]) {
            k = failure[k];
        }
        if (++k == pattern_length) {
            return j - k + 1;
        }
    }
    return std::string::npos;
}
}  // namespace string_search

using string_search::kmp;

/**
 * @brief self-test implementations
 * @returns void
 */
static void tests() {
    assert(kmp("abc1abc12l", "alskfjaldsabc1abc1abc12k2") == std::string::npos);