matchBM : (pat : ByteString) -> (target : ByteString) -> F1 s (List Int) Performs a string search on a `ByteString` utilizing a Boyer-Moore algorithm.
This function finds all (0-based) starting indices of the non-empty pattern `ByteString`
pat within the non-empty target `ByteString`.
Example:
| pat | target |
| ---- | ---------- |
| "AN" | "ANPANMAN" |
| s | window T[s..s+1] | comparisons (right→left) | result | bad-char | good-suffix | chosen shift | next s |
| - | ---------------- | ----------------------------- | --------- | ------------------------- | --------------- | ------------ | ------ |
| 0 | **AN** | j=1: N==N ✓ → j=0: A==A ✓ | **MATCH** | — | (after match) 2 | 2 | 2 |
| 1 | N**P** | j=1: N vs P → mismatch at j=1 | mismatch | lastOcc('P')=-1 → bad = 2 | suffShifts[1]=1 | **2** | 3 |
| 2 | P**A** | j=1: N vs A → mismatch at j=1 | mismatch | lastOcc('A')=0 → bad = 1 | good = 1 | **1** | 3 |
| 3 | **AN** | j=1: N==N ✓ → j=0: A==A ✓ | **MATCH** | — | (after match) 2 | 2 | 5 |
| 4 | N**M** | j=1: N vs M → mismatch at j=1 | mismatch | lastOcc('M')=-1 → bad = 2 | good = 1 | **2** | 6 |
| 5 | M**A** | j=1: N vs A → mismatch at j=1 | mismatch | lastOcc('A')=0 → bad = 1 | good = 1 | **1** | 6 |
| 6 | **AN** | j=1: N==N ✓ → j=0: A==A ✓ | **MATCH** | — | (after match) 2 | 2 | — |
matchBM "AN" "ANPANMAN" => [0, 3, 6]
Totality: total
Visibility: exportindicesBM : (pat : ByteString) -> (target : ByteString) -> F1 s (List Int) Performs a string search on a `ByteString` utilizing a Boyer-Moore algorithm.
This function finds all (0-based) indices (possibly overlapping)
of the non-empty pattern `ByteString` pat
within the non-empty target `ByteString`.
Example:
| pat | target |
| ----- | ----------- |
| "ABC" | "ABCABCABC" |
| Align s | Window | Comparison Result | Chosen Shift | Next s |
| --------- | ------------ | ---------------------------------- | ------------------------------------ | -------- |
| 0 | **ABCABC** | MATCH | good-suffix after full match = 3 | 3 |
| 1 | A**BCABCA** | MISMATCH on last char (`C` vs `A`) | max(bad=2, good=1) = 2 | 3 |
| 2 | AB**CABCAA** | MISMATCH on last char (`C` vs `B`) | max(bad=1, good=1) = 1 | 3 |
| 3 | ABC**ABC** | MATCH | (would shift 3 again) | — |
indicesBM "ABCABC" "ABCABCABC" => [0, 3]
Totality: total
Visibility: exportbreakBM : (pat : ByteString) -> (target : ByteString) -> F1 s (ByteString, ByteString) Splits a ByteString at the first match of pat in target.
This function uses the Boyer–Moore matcher (with overlap = False) to
locate the earliest occurrence of pat in target. If the pattern is
found at index i, the pattern ByteString pat is split at that index,
returning the prefix and suffix as a pair (before, after).
If the pattern does not occur in the target, (pat, empty) is returned.
In other words, the entire pattern becomes the “before” part and the
“after” part is an empty ByteString.
Totality: total
Visibility: exportbreakAfterBM : (pat : ByteString) -> (target : ByteString) -> F1 s (ByteString, ByteString) Splits a ByteString after the first match of pat in target.
This function uses the Boyer–Moore matcher (with overlap = False) to
find the earliest occurrence of pat in target. If the pattern is
found at index i, this function splits pat at position i + length pat,
producing a pair (before, after) that places the entire matched region
into the prefix.
If the pattern does not occur in target, the function returns
(pat, empty), the entire pattern is the “before” substring, and the
suffix is empty.
Totality: total
Visibility: exportsplitKeepFrontBM : (pat : ByteString) -> (target : ByteString) -> F1 s (List ByteString) Splits a ByteString into a list of pieces according to repeated
matches of target, keeping the matching prefix of pat
at the front of each produced chunk.
This function repeatedly searches target for occurrences of pat
(using the Boyer–Moore matcher with overlap = False). Each time a
match is found at index i, the prefix of pat up to i + length pat
is emitted as the next chunk, and the function continues processing the
remaining suffix of pat.
Unlike breakBM or breakAfterBM, this function performs repeated
splitting until the entire pattern has been consumed, producing a
list of ByteStrings.
Totality: total
Visibility: exportsplitKeepEndBM : (pat : ByteString) -> (target : ByteString) -> F1 s (List ByteString) Splits a ByteString into a list of pieces according to repeated
matches of pat inside target, keeping the matching
suffix of pat at the end of each produced chunk.
This function repeatedly searches target for occurrences of pat
(using the Boyer–Moore matcher with overlap = False). Each time a
match is found at index i, the next chunk emitted is the prefix of
target of length i + length pat, which includes the entire matched
occurrence of pat at its end.
After emitting this chunk, the function continues splitting the
remainder of target until all input has been consumed.
Unlike splitKeepFrontBM, which keeps the matched prefix of pat
at the front of each chunk, splitKeepEndBM ensures the match
appears at the end of each chunk.
If pat does not occur in target, the result is a singleton list
containing the original target.
Totality: total
Visibility: exportsplitDropBM : (pat : ByteString) -> (target : ByteString) -> F1 s (List ByteString) Splits a ByteString into a list of pieces according to repeated
matches of pat inside target, dropping each matched
occurrence from the output entirely.
This function repeatedly searches target for occurrences of pat
(using the Boyer–Moore matcher with overlap = False). Each time a
match is found at index i, the prefix of target of length i
(that is, the portion preceding the match) is emitted as the next
chunk. The matched substring itself is not included.
After emitting this prefix, the function continues splitting the
remainder of target, skipping over the full match of length
i + length pat. This process continues until the entire target
has been consumed.
Unlike splitKeepFrontBM and splitKeepEndBM, which include the
matched pattern in each emitted chunk, splitDropBM removes all
occurrences of pat from the output.
If pat does not occur in target, the result is a singleton list
containing the original target.
Totality: total
Visibility: exportreplaceBM : (pat : ByteString) -> ByteString -> (target : ByteString) -> F1 s (List ByteString) Replaces all non-overlapping occurrences of a pattern in a ByteString
using the Boyer–Moore matcher.
This function repeatedly searches target for occurrences of pat
(using matcher False). Each time a match is found at index i:
* If i == 0, the match is at the current position. The matched
segment is dropped and sub is appended to the result (unless
sub is empty, in which case nothing is appended).
* If i > 0, the prefix take i target is appended to the result,
followed by sub (unless sub is empty). The matched segment is
then dropped and processing continues on the remaining suffix.
If no further matches are found, the remaining target is appended
unchanged and the result is returned.
The result is accumulated via a `SnocList` and returned as a `List
ByteString`, preserving left-to-right order of the produced chunks.
Totality: total
Visibility: export