A Kotlin Multiplatform port of Perl's Regexp::Trie: builds an optimized regular expression from a set of words, using a trie to factor out common prefixes.

foobar|fooxar|foozap|fooza      # naive alternation: backtracks on every word
(?:foo(?:bar|xar|zap?))         # kotlin-regexp-trie: shares the "foo" prefix

Matching a large keyword list with a naive alternation forces the regex engine to re-try each alternative from the same position. The trie-generated pattern shares common prefixes, which makes matching dramatically faster for large word lists.

Don't need a Regex — just the matches? For huge dictionaries, all (possibly overlapping) occurrences, or cheap "contains any?" screening, use the sister library kotlin-aho-corasick: an Aho-Corasick automaton whose scan cost is independent of the dictionary size. Use this library when you want a real Regex to combine with boundaries, flags or a larger pattern.

// build.gradle.kts
dependencies {
    implementation("dev.hsbrysk:regexp-trie:<version>")
}

For a Kotlin Multiplatform project, add it to commonMain:

kotlin {
    sourceSets {
        commonMain.dependencies {
            implementation("dev.hsbrysk:regexp-trie:<version>")
        }
    }
}

import dev.hsbrysk.regexptrie.RegexpTrie

// One-shot: build a Regex from words
val regex = RegexpTrie.union("foobar", "fooxar", "foozap", "fooza")
regex.containsMatchIn("I said foozap!")  // true

// Constructor
val trie = RegexpTrie("foobar", "fooxar", "foozap", "fooza")

// DSL style
val trie2 = buildRegexpTrie {
    +"foobar"
    +"fooxar"
    addAll(listOf("foozap", "fooza"))
}

// Incremental
val trie3 = RegexpTrie()
    .add("foobar")
    .addAll(listOf("fooxar", "foozap", "fooza"))

trie.toRegexString()                     // "(?:foo(?:bar|xar|zap?))"
trie.toRegex()                           // Regex
trie.toRegex(RegexOption.IGNORE_CASE)    // Regex with options

// Embed the pattern in a larger expression
val anchored = Regex("^" + trie.toRegexString() + "$")

• Deterministic output — the generated pattern depends only on the set of words, not on their insertion order.
• Safe to embed — the pattern is always wrapped in a non-capturing group and contains no capturing groups.
• Empty trie — produces (?!), a pattern that matches nothing. So RegexpTrie.union(emptyList()) is a Regex that never matches. (This is the one pattern you should not append a quantifier to when embedding: (?!)? matches the empty string.)
• Empty string — adding "" makes the whole pattern optional, e.g. RegexpTrie("foo", "") produces (?:(?:foo)?).
• Character classes — sibling single-character branches are merged into a character class, and runs of 3+ consecutive code points above U+00FF collapse into ranges: RegexpTrie("ぁ", "あ", "ぃ") produces (?:[ぁ-ぃ]). ASCII/Latin-1 runs intentionally stay flat (RegexpTrie("a", "b", "c") produces (?:[abc])): below U+0100 the JVM compiles an enumerated class to a bitmap with O(1) membership tests, which beats a range.
• Portable escaping — each regex meta character is escaped individually (no platform-specific constructs like the JVM's \Q...\E), so the generated pattern is identical and valid on every Kotlin platform.
• Code-point aware — words are processed per code point, so surrogate pairs (e.g. emoji) are never split across a character class: RegexpTrie("😀", "😁") produces (?:😀|😁), not a broken [😀😁].

Scanning text for a 1,000-word keyword list is ~22× faster on the JVM, ~41× on Kotlin/Native and ~69× on Wasm than a naive word1|word2|... alternation (on JS the gap is marginal because V8 already optimizes alternations aggressively). Character-class ranges — applied only above U+00FF — are ~17% faster than flat classes on the JVM and identical elsewhere, while shrinking the pattern by ~66% on range-friendly vocabularies such as sequential kana ids; ASCII classes stay flat to keep the JVM's bitmap fast path. See benchmark/RESULTS.md for full results and methodology.

All Kotlin targets. The implementation is pure common code with zero dependencies.

This library follows a long line of Regexp::Trie ports and trie-based regex generators:

• Regexp::Trie (Perl) by Dan Kogai — the original this library is ported from; see also the more feature-rich Regexp::Assemble
• regexp-opt (Emacs Lisp) — the same idea, built into Emacs since the 1990s for Font Lock keywords
• regexp_trie (Ruby) by gfx
• regexp-trie (Java) by tokuhirom
• php-regexp-trie (PHP) by sters
• regex-trie (JavaScript) by alexeld
• regexgen (JavaScript) by Devon Govett — goes further with DFA minimization (shared suffixes, not just prefixes)
• trieregex / triegex / trrex (Python)
• frak (Clojure)

MIT License