<commit_before>(ns strmatch.logic.kmp-matcher
  (:use [strmatch.logic.common :only [discrepancy-index color-array]]))

; Implementation of the KMP algorithm for string matching.
; http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

(defn- proper-prefixes [lst]
  (map #(take % lst)
       (range 1 (count lst))))

(defn- proper-suffixes [lst]
  (map #(drop % lst)
       (range 1 (count lst))))

(defn- prefix? [candidate string]
  (= candidate (take (count candidate) string)))

(defn- fail-value [needle suffix]
  (count (first (filter #(prefix? % needle)
                        (proper-suffixes suffix)))))

; Calculates the failure array.
; The value at every index i is the length of the 
; longest proper suffix of `(take i needle)` which is
; also a prefix of `needle`.
; For convenience, the first value is always -1.
(defn failure-array [needle]
  (let [chars (seq needle)
        heads (proper-prefixes chars)]
    (vec (cons -1 (map #(fail-value needle %) heads)))))

(defn- entry-for [index discrep needle already-matched]
  (let [to-ignore (max 0 already-matched)
        padding (+ to-ignore index)
        length-of-match (if discrep (- discrep to-ignore) (count needle))]
    {:index index
     :colors (color-array padding length-of-match)}))

(defn match
  ([needle haystack] (vec (reverse (match needle haystack (failure-array needle) 0 nil 0))))
  ([needle haystack fail-array index result prev-fail]
   (let [discrep (discrepancy-index needle haystack index)
         jump (- discrep (fail-array discrep))
         next-entry (entry-for index discrep needle prev-fail)
         next-result (cons next-entry result)]
     (if (and discrep (<= index (count haystack)))
       (recur needle haystack fail-array (+ index jump) next-result (fail-array discrep))
       next-result))))<commit_msg>refactor KMP more<commit_after>(ns strmatch.logic.kmp-matcher
  (:use [strmatch.logic.common :only [discrepancy-index color-array]]))

; Implementation of the KMP algorithm for string matching.
; http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

(defn- proper-prefixes [lst]
  (map #(take % lst)
       (range 1 (count lst))))

(defn- proper-suffixes [lst]
  (map #(drop % lst)
       (range 1 (count lst))))

(defn- prefix? [candidate string]
  (= candidate (take (count candidate) string)))

(defn- fail-value [needle suffix]
  (count (first (filter #(prefix? % needle)
                        (proper-suffixes suffix)))))

; Calculates the failure array.
; The value at every index i is the length of the 
; longest proper suffix of `(take i needle)` which is
; also a prefix of `needle`.
; For convenience, the first value is always -1.
(defn failure-array [needle]
  (let [chars (seq needle)
        heads (proper-prefixes chars)]
    (vec (cons -1 (map #(fail-value needle %) heads)))))

(defn- entry-for [index discrep needle already-matched]
  (let [to-ignore (max 0 already-matched)
        padding (+ to-ignore index)
        length-of-match (if discrep (- discrep to-ignore) (count needle))]
    {:index index
     :colors (color-array padding length-of-match)}))

(defn match
  [needle haystack]
  (let [fail-array (failure-array needle)]
    (loop [index 0
           result []
           prev-fail 0]
      (let [discrep (discrepancy-index needle haystack index)
            jump (- discrep (fail-array discrep))
            next-index (+ index jump)
            next-entry (entry-for index discrep needle prev-fail)
            next-result (conj result next-entry)
            not-done (and discrep (<= index (count haystack)))]
        (if not-done
          (recur next-index next-result (fail-array discrep))
          next-result)))))
{'fraction_non_alphanumeric': 0.13220247711362412, 'fraction_numerical': 0.009154550350026925, 'mean_word_length': 3.086908690869087, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 3, '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': '3420276', 'n_tokens_mistral': 1225, 'n_tokens_neox': 1162, 'n_words': 382}