Suffix Array Search

Searching a large text repeatedly for different patterns with a plain scan (StringFind in a loop) costs O(text length) every single query, no matter how many times the same text gets searched. This library builds an actual suffix array once - every starting position in the text, sorted by the suffix it begins - so that every occurrence of a pattern corresponds to one CONTIGUOUS block in the sorted array. Finding that block with two binary searches costs O(log n * pattern length) per query after the one-time build, which is the entire point of paying the build cost up front for a text that will be queried many times. Build() sorts suffixes by comparing them as actual substrings via StringCompare() - genuinely correct, but O(n) per comparison in the worst case, making construction O(n^2 log n) overall rather than the O(n log n)-total prefix-doubling or O(n) SA-IS algorithms used in production text-indexing engines. That trade-off is stated plainly: this is sized for moderate texts (comfortably a few thousand characters - symbol lists, log excerpts, comment strings), not for indexing megabyte-scale corpora. The LCP (longest common prefix) array built alongside the suffix array gives LongestRepeatedSubstring() essentially for free: the maximum adjacent-suffix LCP value IS the longest substring that repeats anywhere in the text, a classic and genuinely useful suffix- array by-product, not a bolted-on extra. Every demo query is cross-checked against a naive StringFind() loop so the suffix array's answers are proven correct, not just plausible. Notes and limitations - Construction is O(n^2 log n) worst case (substring-comparison quicksort, non-randomised pivot). Fine for texts up to a few thousand characters; not intended for indexing very large corpora. - The index is a snapshot of the text passed to Build() - it does not track further changes. Call Build() again after the text changes. - Occurrences returned by FindOccurrences() can overlap (e.g. searching "aa" in "aaa" returns two overlapping matches at positions 0 and 1), matching the naive StringFind()-loop cross-check used in the demo, not a non-overlapping match count. - Not thread-safe beyond what a single MQL4 program thread already guarantees.

Script · MT5 · v1.0 · Free

Tags: MT5 Script · MQL5 Source Code

MQL4 & MQL5 scripts · PolyMaria