str_matching.h

Go to the documentation of this file.

// Document this file
# pragma once

#include <string>
#include <cmath>
#include <climits>

#include <iostream>
using namespace std;

namespace alglib {
namespace string {

size_t naive_str_matching(const std::string& text, const std::string& pattern) {
    int s = 0;
    int n = text.length(), m = pattern.length();
    for(s = 0; s <= n - m; s++)
        // Loop Invariant : The pattern doesn't exist in T[0:s-1] but may exist
        // in T[s, n].
        if(text.substr(s, m) == pattern)
            return s;

    return std::string::npos;

}

// Helper procedure for rabin-karp algorithm
static long int poly_hash(const std::string& input, int m) {
    const int radix = 10;
    const long int Q = 997;
    long int hash_val = 0;
    for(int i = 0; i < m; i++)
        hash_val = (hash_val * radix + input[i]) % Q;
    return hash_val;
}

size_t rabin_karp(const std::string& text, const std::string& pattern) {
    int m = pattern.length();
    int n = text.length();
    const long int R = 10;
    long int pattern_hash = poly_hash(pattern, m);
    long int text_hash = poly_hash(text, m);
    long int R_m_minus_1 = std::pow(R, m - 1);

    if(pattern_hash == text_hash)
        if(pattern == text.substr(0, m))
            return 0;
    for(int s = 1; s <= n - m; s++) {
        text_hash = (text_hash - R_m_minus_1 * text[s-1]) * R + text[s + m - 1];
        if(pattern_hash == text_hash)
            if(pattern == text.substr(s, m))
                return s;
    }

    return std::string::npos;
}




size_t horspool(const std::string& text, const std::string& pattern) {

    int skip_table[UCHAR_MAX + 1];
    int n = text.length(), m = pattern.length();

    // Initialize each of the index of the shift table to m.
    std::fill_n(skip_table, UCHAR_MAX + 1, m);
    
    // Compute the skip table for the given pattern.
    for(int i = 0; i < m - 1; i++) {
        skip_table[pattern[i]] = m - i - 1;
    }

    // Do the string comparison

    // align the pattern shifted with s in [0, n-m] with the text
    for(int shift = 0; shift <= n - m;) {

        // For every shift, start comparing from back
        int i = m - 1;

        // Keep moving to the right until a mismatch is detected.
        while(i >= 0 && (text[shift + i] == pattern[i]))
            i--;
        
        if(i == -1)
            // if the pattern matched completely with the text
            return shift;
            
        shift += skip_table[text[shift + m - 1]];
    }

    return std::string::npos;

}

size_t kmp(const std::string& text, const std::string& pattern) {


}



}  // end string namespace
}  // end alglib namespace