Problems Base course RU

Solves

string matching

Articles

STR Algorithm The Aho–Corasick algorithm Every occurrence of thousands of words in one pass: a trie of the words plus failure links, as in the prefix function. O(n + Σ|wᵢ| + z) 1 problem STR Algorithm Boyer–Moore Compares from right to left and skips letters: on long patterns it reads only a small part of the text. O(n + m) 2 problems STR Algorithm The Burrows–Wheeler transform A permutation that compresses a text and serves as an index to it: backward search, LF, and read alignment. O(m) to count a pattern, O(m + k·s) for k positions 2 problems STR Data structure BK-tree All passwords one or two edits from a given one: the triangle inequality cuts off whole branches, and where it stops helping. O(N · depth) to build 1 problem

Problems

How many schemata survive How much Horspool reads A genome's suffixes by digits Counting in the transform The good suffix table How many times each word Where the reads land Where the ring begins

Often together

in production 3 security 2 bioinformatics 2 classic 2 automaton 1 trie 1 streaming 1 networks 1 contests 1 precomputation 1 text editors 1 operating systems 1