<commit_before>///////////////////////////////////////////////////////////////////////////////
//  Z-functions
/////////////////////////////////////////////////////////////////////////////// 

#include <iostream>
#include <string>
#include <vector>

using namespace std;

// z-functions: return z, z[i] is the length of the longest substring
//              starting from S[i] which is also a prefix of S

vector<int> get_ZFunction(string s){
    int len = s.length();
    vector<int> z(len);
    int L = 0, R = 0;
    for(int i = 1; i < len; i++ ){
        if (i > R){
            L = R = i;
            while (R < len && s[R-L] == s[R]) R++;
            z[i] = R - L; R--;
        } else {
            int k = i - L;
            if(z[k] < R - i + 1) z[i] = z[k];
            else {
                L = i;
                while (R < len && s[R - L] == s[R]) R++;
                z[i] = R - L; R--;
            }
        }
    }
    z[0] = len;
    return z;
}


///////////////////////////////////////////////////////////////////////////////
//  Knuth-Morris-Pratt
///////////////////////////////////////////////////////////////////////////////

/* 
  Searches for the string w in the string s (of length k). Returns the 
  0-based index of the first match (k if no match is found). Algorithm 
  runs in O(k) time. 
*/ 

#include <cassert>

using namespace std;
typedef vector<int> VI;

class KnuthMorrisPratt {
public:
    void build_table(string& w, VI& t){
        int sz = w.size();
        t = VI(sz);
        int i = 2, j = 0;
        t[0] = -1; t[1] = 0;
        while (i < sz) {
            if (w[i - 1] == w[j]) { t[i] = j + 1; i++; j++; }
            else if (j > 0) j = t[j];
            else { t[i] = 0; i++; }
        }
    }

    // returh the index of the first match, or the length of s if w is not found
    int KMP(string s, string w){
        int m = 0, i = 0;
        VI t;
        build_table(w, t);
        int sz_s = s.size();
        int sz_w = w.size();
        while (m+i < sz_s) {
            if (w[i] == s[m+i]) {
                i++;
                if (i == sz_w) return m;
            } else {
                m += i - t[i];
                if (i > 0) i = t[i];
            }
        }
        return s.length();
    }
};

int main(){
    KnuthMorrisPratt solve;
    assert(solve.KMP("win", "I wanna win.") == 3);
    assert(solve.KMP("I wanna win.", "win") == 8);
    return 0;
}  

///////////////////////////////////////////////////////////////////////////////
//  Prefix Function
//  Given a string. Return an array of numbers, 
//  where is defined as follows: it is a maximum length of the longest 
//  proper suffix substring that matches the prefix (suffix own - so not 
//  the entire line). In particular, the value is set equal to zero.
//  For example, the string "abcabcd" prefix function is: [1, 0, 0, 1, 2, 3, 0]
///////////////////////////////////////////////////////////////////////////////

vector<int> prefix_function (string s){
    int n = (int) s.length();
    vector<int> pi (n);
    pi[0] = 1;
    for (int i=1; i<n; ++i){
        int j = pi[i-1];
        while (j > 0 && s[i] != s[j])
            j = pi[j-1];
        if (s[i] == s[j])  ++j;
        pi[i] = j;
    }
    return pi;
}<commit_msg>Fixed StringMatching.cpp<commit_after>///////////////////////////////////////////////////////////////////////////////
//  Z-functions
/////////////////////////////////////////////////////////////////////////////// 

#include <iostream>
#include <string>
#include <vector>

using namespace std;

// z-functions: return z, z[i] is the length of the longest substring
//              starting from S[i] which is also a prefix of S

vector<int> get_ZFunction(string s){
    int len = s.length();
    vector<int> z(len);
    int L = 0, R = 0;
    for(int i = 1; i < len; i++ ){
        if (i > R){
            L = R = i;
            while (R < len && s[R-L] == s[R]) R++;
            z[i] = R - L; R--;
        } else {
            int k = i - L;
            if(z[k] < R - i + 1) z[i] = z[k];
            else {
                L = i;
                while (R < len && s[R - L] == s[R]) R++;
                z[i] = R - L; R--;
            }
        }
    }
    z[0] = len;
    return z;
}


///////////////////////////////////////////////////////////////////////////////
//  Knuth-Morris-Pratt
///////////////////////////////////////////////////////////////////////////////

/* 
  Searches for the string w in the string s (of length k). Returns the 
  0-based index of the first match (k if no match is found). Algorithm 
  runs in O(k) time. 
*/ 

#include <cassert>

using namespace std;
typedef vector<int> VI;

class KnuthMorrisPratt {
public:
    void build_table(string& w, VI& t){
        int sz = w.size();
        t = VI(sz);
        int i = 2, j = 0;
        t[0] = -1; t[1] = 0;
        while (i < sz) {
            if (w[i - 1] == w[j]) { t[i] = j + 1; i++; j++; }
            else if (j > 0) j = t[j];
            else { t[i] = 0; i++; }
        }
    }

    // returh the index of the first match, or the length of s if w is not found
    int KMP(string s, string w){
        int m = 0, i = 0;
        VI t;
        build_table(w, t);
        int sz_s = s.size();
        int sz_w = w.size();
        while (m+i < sz_s) {
            if (w[i] == s[m+i]) {
                i++;
                if (i == sz_w) return m;
            } else {
                m += i - t[i];
                if (i > 0) i = t[i];
            }
        }
        return s.length();
    }
};

int main(){
    KnuthMorrisPratt solve;
    assert(solve.KMP("win", "I wanna win.") == 3);
    assert(solve.KMP("I wanna win.", "win") == 8);
    return 0;
}  

///////////////////////////////////////////////////////////////////////////////
//  Prefix Function
//  Given a string. Return an array of numbers, 
//  where is defined as follows: it is a maximum length of the longest 
//  proper suffix substring that matches the prefix (suffix own - so not 
//  the entire line). In particular, the value is set equal to zero.
//  For example, the string "abcabcd" prefix function is: [1, 0, 0, 1, 2, 3, 0]
///////////////////////////////////////////////////////////////////////////////

vector<int> prefix_function (string s){
    int n = (int) s.length();
    vector<int> pi (n);
    for (int i=1; i<n; ++i){
        int j = pi[i-1];
        while (j > 0 && s[i] != s[j])
            j = pi[j-1];
        if (s[i] == s[j])  ++j;
        pi[i] = j;
    }
    return pi;
}
{'fraction_non_alphanumeric': 0.2826153846153846, 'fraction_numerical': 0.010461538461538461, 'mean_word_length': 1.0533796588755528, 'pattern_counts': {'":': 0, '<': 35, '<?xml version=': 0, '>': 29, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1539872', 'n_tokens_mistral': 2130, 'n_tokens_neox': 2037, 'n_words': 709}