Aho–Corasick matching.

// A bounded, inspectable teaching implementation. No external dependencies.
export const MAX_TERMS = 12;
export const MAX_TERM_SCALARS = 24;
export const MAX_TEXT_SCALARS = 240;

export type Hit = { term: string; start: number; end: number };

export type GlossaryErrorCode =
	'term-count' | 'empty-term' | 'long-term' | 'duplicate-term' | 'long-text' | 'malformed-text';

export class GlossaryError extends Error {
	code: GlossaryErrorCode;
	constructor(code: GlossaryErrorCode, message: string) {
		super(message);
		this.name = 'GlossaryError';
		this.code = code;
	}
}

export type State = {
	prefix: string; // the symbols that lead here from the root, kept for inspection
	next: Map<string, number>;
	fail: number; // the longest proper suffix of prefix that is also a prefix in the trie
	term: number | null; // the term that ends exactly here
	output: number; // the nearest state along failure links that ends a term, or -1
};
export type Glossary = { terms: string[]; lengths: number[]; states: State[] };

// Unicode scalar values. Checks the whole text first, then the length.
function scalars(text: string, limit: number, code: GlossaryErrorCode, label: string): string[] {
	const result = Array.from(text);
	for (const symbol of result) {
		const point = symbol.codePointAt(0)!;
		if (point >= 0xd800 && point <= 0xdfff)
			throw new GlossaryError('malformed-text', `${label} must be well-formed Unicode.`);
	}
	if (result.length > limit)
		throw new GlossaryError(code, `${label} is limited to ${limit} Unicode scalar values.`);
	return result;
}

const state = (prefix: string): State => ({
	prefix,
	next: new Map(),
	fail: 0,
	term: null,
	output: -1
});

export function buildGlossary(terms: readonly string[]): Glossary {
	if (terms.length < 1 || terms.length > MAX_TERMS)
		throw new GlossaryError('term-count', `Use 1 to ${MAX_TERMS} terms.`);
	const glossary: Glossary = { terms: [...terms], lengths: [], states: [state('')] };
	const seen = new Set<string>();
	terms.forEach((term, index) => {
		if (term === '') throw new GlossaryError('empty-term', 'Terms cannot be empty.');
		const symbols = scalars(term, MAX_TERM_SCALARS, 'long-term', 'A term');
		if (seen.has(term)) throw new GlossaryError('duplicate-term', `“${term}” appears twice.`);
		seen.add(term);
		let current = 0;
		for (const symbol of symbols) {
			let next = glossary.states[current].next.get(symbol);
			if (next === undefined) {
				// A new branch. Terms that share a beginning share these states.
				next = glossary.states.length;
				glossary.states[current].next.set(symbol, next);
				glossary.states.push(state(glossary.states[current].prefix + symbol));
			}
			current = next;
		}
		glossary.states[current].term = index;
		glossary.lengths.push(symbols.length);
	});
	linkFailures(glossary);
	return glossary;
}

function linkFailures({ states }: Glossary): void {
	// Breadth-first: every failure target is shallower, so it is already linked.
	const queue = [...states[0].next.values()]; // one-symbol states fail to the root
	for (let head = 0; head < queue.length; head++) {
		const parent = queue[head];
		for (const [symbol, child] of states[parent].next) {
			queue.push(child);
			let fallback = states[parent].fail;
			while (fallback !== 0 && !states[fallback].next.has(symbol)) fallback = states[fallback].fail;
			const fail = states[fallback].next.get(symbol) ?? 0;
			states[child].fail = fail;
			// Point at the nearest term along the failure chain instead of copying its outputs.
			states[child].output = states[fail].term !== null ? fail : states[fail].output;
		}
	}
}

export function scan(glossary: Glossary, text: string): Hit[] {
	const symbols = scalars(text, MAX_TEXT_SCALARS, 'long-text', 'The document');
	const { states, terms, lengths } = glossary;
	const hits: Hit[] = [];
	let current = 0;
	symbols.forEach((symbol, index) => {
		// Fall back along failure links. The document cursor never moves backward.
		while (current !== 0 && !states[current].next.has(symbol)) current = states[current].fail;
		current = states[current].next.get(symbol) ?? 0;
		// The term that ends here, then every shorter term that ends here too.
		let at = states[current].term !== null ? current : states[current].output;
		for (; at !== -1; at = states[at].output) {
			const term = states[at].term!;
			hits.push({ term: terms[term], start: index + 1 - lengths[term], end: index + 1 });
		}
	});
	// Terms are unique, so start then end decides every tie.
	return hits.sort((a, b) => a.start - b.start || a.end - b.end);
}

export function findAll(terms: readonly string[], text: string): Hit[] {
	return scan(buildGlossary(terms), text);
}

export type Step = {
	index: number;
	symbol: string;
	from: number;
	fallbacks: number[]; // states visited through failure links before the next transition
	to: number;
	hits: Hit[];
};

// The same walk as scan, recorded one symbol at a time for the lesson's story and lab.
export function trace(glossary: Glossary, text: string): Step[] {
	const symbols = scalars(text, MAX_TEXT_SCALARS, 'long-text', 'The document');
	const { states, terms, lengths } = glossary;
	const steps: Step[] = [];
	let current = 0;
	symbols.forEach((symbol, index) => {
		const from = current;
		const fallbacks: number[] = [];
		while (current !== 0 && !states[current].next.has(symbol)) {
			current = states[current].fail;
			fallbacks.push(current);
		}
		current = states[current].next.get(symbol) ?? 0;
		const hits: Hit[] = [];
		let at = states[current].term !== null ? current : states[current].output;
		for (; at !== -1; at = states[at].output) {
			const term = states[at].term!;
			hits.push({ term: terms[term], start: index + 1 - lengths[term], end: index + 1 });
		}
		steps.push({ index, symbol, from, fallbacks, to: current, hits });
	});
	return steps;
}

export const supportGlossary = ['auth', 'author', 'queue', 'retry'];
export const supportDocument = 'The author retries the queue after auth.';

export function runExample(): void {
	const glossary = buildGlossary(supportGlossary); // build once
	for (const document of [supportDocument, 'Retry the queue, then check auth.']) {
		const hits = scan(glossary, document); // scan every document
		console.log(hits.map((hit) => `${hit.term}@${hit.start}-${hit.end}`).join(' ') || 'no terms');
	}
}

runExample();

// A bounded, inspectable teaching implementation. No external dependencies.
package main

import (
	"fmt"
	"sort"
	"strings"
	"unicode/utf8"
)

const (
	MaxTerms       = 12
	MaxTermScalars = 24
	MaxTextScalars = 240
)

type Hit struct {
	Term       string
	Start, End int
}

// GlossaryError carries the same codes as the TypeScript version.
type GlossaryError struct {
	Code    string
	Message string
}

func (e *GlossaryError) Error() string { return e.Message }

type State struct {
	Prefix string // the symbols that lead here from the root, kept for inspection
	Next   map[rune]int
	Fail   int // the longest proper suffix of Prefix that is also a prefix in the trie
	Term   int // the term that ends exactly here, or -1
	Output int // the nearest state along failure links that ends a term, or -1
}

type Glossary struct {
	Terms   []string
	Lengths []int
	States  []State
}

func newState(prefix string) State {
	return State{Prefix: prefix, Next: map[rune]int{}, Term: -1, Output: -1}
}

func BuildGlossary(terms []string) (*Glossary, error) {
	if len(terms) < 1 || len(terms) > MaxTerms {
		return nil, &GlossaryError{"term-count", fmt.Sprintf("use 1 to %d terms", MaxTerms)}
	}
	g := &Glossary{Terms: append([]string(nil), terms...), States: []State{newState("")}}
	seen := map[string]bool{}
	for index, term := range terms {
		if term == "" {
			return nil, &GlossaryError{"empty-term", "terms cannot be empty"}
		}
		if !utf8.ValidString(term) {
			return nil, &GlossaryError{"malformed-text", "a term must be valid UTF-8"}
		}
		length := utf8.RuneCountInString(term)
		if length > MaxTermScalars {
			return nil, &GlossaryError{"long-term", fmt.Sprintf("a term is limited to %d Unicode scalar values", MaxTermScalars)}
		}
		if seen[term] {
			return nil, &GlossaryError{"duplicate-term", fmt.Sprintf("%q appears twice", term)}
		}
		seen[term] = true
		current := 0
		for _, symbol := range term {
			next, ok := g.States[current].Next[symbol]
			if !ok {
				// A new branch. Terms that share a beginning share these states.
				next = len(g.States)
				g.States[current].Next[symbol] = next
				g.States = append(g.States, newState(g.States[current].Prefix+string(symbol)))
			}
			current = next
		}
		g.States[current].Term = index
		g.Lengths = append(g.Lengths, length)
	}
	g.linkFailures()
	return g, nil
}


func (g *Glossary) linkFailures() {
	states := g.States
	// Breadth-first: every failure target is shallower, so it is already linked.
	queue := make([]int, 0, len(states))
	for _, child := range states[0].Next { // one-symbol states fail to the root
		queue = append(queue, child)
	}
	for head := 0; head < len(queue); head++ {
		parent := queue[head]
		for symbol, child := range states[parent].Next {
			queue = append(queue, child)
			fallback := states[parent].Fail
			for fallback != 0 {
				if _, ok := states[fallback].Next[symbol]; ok {
					break
				}
				fallback = states[fallback].Fail
			}
			fail := states[fallback].Next[symbol] // 0, the root, when absent
			states[child].Fail = fail
			// Point at the nearest term along the failure chain instead of copying its outputs.
			if states[fail].Term != -1 {
				states[child].Output = fail
			} else {
				states[child].Output = states[fail].Output
			}
		}
	}
}


func (g *Glossary) Scan(text string) ([]Hit, error) {
	if !utf8.ValidString(text) {
		return nil, &GlossaryError{"malformed-text", "the document must be valid UTF-8"}
	}
	if utf8.RuneCountInString(text) > MaxTextScalars {
		return nil, &GlossaryError{"long-text", fmt.Sprintf("the document is limited to %d Unicode scalar values", MaxTextScalars)}
	}
	hits := []Hit{}
	current, index := 0, 0
	for _, symbol := range text {
		// Fall back along failure links. The document cursor never moves backward.
		for current != 0 {
			if _, ok := g.States[current].Next[symbol]; ok {
				break
			}
			current = g.States[current].Fail
		}
		current = g.States[current].Next[symbol]
		// The term that ends here, then every shorter term that ends here too.
		at := g.States[current].Output
		if g.States[current].Term != -1 {
			at = current
		}
		for ; at != -1; at = g.States[at].Output {
			term := g.States[at].Term
			hits = append(hits, Hit{g.Terms[term], index + 1 - g.Lengths[term], index + 1})
		}
		index++
	}
	// Terms are unique, so start then end decides every tie.
	sort.SliceStable(hits, func(a, b int) bool {
		if hits[a].Start != hits[b].Start {
			return hits[a].Start < hits[b].Start
		}
		return hits[a].End < hits[b].End
	})
	return hits, nil
}


func FindAll(terms []string, text string) ([]Hit, error) {
	g, err := BuildGlossary(terms)
	if err != nil {
		return nil, err
	}
	return g.Scan(text)
}

func format(hits []Hit) string {
	if len(hits) == 0 {
		return "no terms"
	}
	parts := make([]string, len(hits))
	for i, hit := range hits {
		parts[i] = fmt.Sprintf("%s@%d-%d", hit.Term, hit.Start, hit.End)
	}
	return strings.Join(parts, " ")
}

var supportGlossary = []string{"auth", "author", "queue", "retry"}

const supportDocument = "The author retries the queue after auth."

func main() {
	glossary, err := BuildGlossary(supportGlossary) // build once
	if err != nil {
		fmt.Println(err)
		return
	}
	for _, document := range []string{supportDocument, "Retry the queue, then check auth."} {
		hits, err := glossary.Scan(document) // scan every document
		if err != nil {
			fmt.Println(err)
			return
		}
		fmt.Println(format(hits))
	}
}