Basic Definitions for Strings. String Algorithms

Automated text processing has lost none of its relevance. The need for it arises both in solving the simplest applied problems and in actively developing fields of science, such as genetics. DNA chain analysis, compiler development, implementation of full-text search in DBMSs, dictionary-based data compression methods, and, finally, small programs for the mundane editing of product descriptions in a database – all of these are areas where string algorithms are applied. First of all, the basic terms used in this section should be defined. A symbol here is a rather broad concept – it is an information unit of a certain type, to which, as a rule, some printed form is assigned.

Basic definitions

Alphabet –.Alphabet (Eng. alphabet) — a finite non-empty set of symbols. Let us agree to denote the alphabet by a capital Greek letter

The following alphabets are most commonly used:

• Σ={0,1} — the binary alphabet.
• Σ={a,b,…,z} — the set of lowercase letters of the English alphabet.
• Σ={0,1,2,…,9} — the alphabet of digits.
• Σ={⋅,−} — the alphabet underlying Morse code.
• Musical notation symbols

Symbol (Eng. symbol) — an object having its own content and a unique readable form.

String (word) – a sequence of symbols of some alphabet.

String length – the number of symbols in a string. Chain length (Eng. string length) — the number of symbols in a chain. The length of a chain w is usually denoted |w|.

A string is denoted by symbols of the alphabet, for example – a string of length n, where x[i] is the i-th symbol. The length of a string x is usually denoted |x|.

Σk — the set of chains of length k over the alphabet Σ .

— the set of all chains over the alphabet Σ .

Concatenation – joining, the operation of «gluing» strings together. The concatenation of strings x and y is denoted xy.

Let . Then α⋅β or αβ denotes their concatenation (Eng. concatenation), that is, the chain in which the chains α and β are written one after another.

Empty string – a string containing no symbols. Empty chain (Eng. empty string) — a chain containing no symbols. This chain, denoted ε , can be regarded as a chain in any alphabet. For any string the following holds: .

The set of strings with the operation of concatenation and the neutral element the empty string forms a free monoid.

Substring – a certain non-empty sequence of consecutive symbols of a string. A string x is called a substring of string y if there exist
strings z1 and z2 such that .

Prefix – a certain beginning of a string. A prefix p of string t – a string such that pv=t for some (possibly empty) string v. A prefix is called
proper if .

Suffix – a certain ending of a string. A suffix s of string t – a string such that vs=t for some (possibly empty) string v. A suffix is called
proper if

Relations between strings

Definition: Prefix (Eng. prefix) of string β — a string α:β=αγ

Let , then α=abr — a prefix of β .

Definition: Suffix (Eng. suffix) of string ββ — a string α:β=γα .

Let β= , then α=bra — a suffix of β.

Definition: Border (Eng. circumfix) of string β — a string

Let , then α=abra — a border of β.

Definition: α[i] — the symbol of string α located at the i-th position.

Let , then .

Definition: Period (Eng. period) of string αα — a number .

Let , then p=3 — the period of string α=acaacaa .

Claim:

Suppose the string ττ — the period αα and |α||α| are known, then the entire string αα can be reconstructed.

From the definition of the period of a string it follows that

Thus .

Definition: A string α≠ε with period p≠|α| , is called strongly periodic if |α|modp=0 .

The string α=acaacaaca is strongly periodic with period p=3

Definition: Substring (Eng. substring) — a certain non-empty subsequence of consecutive symbols of a string.

Let then α=aca — a substring of string β.

Definition: A non-empty string of the form αα is called a tandem repeat (Eng. repetition).

Definition: A palindrome (Eng. Palindrome) is a string of the form — the reversed string α, c — any symbol.

Definition: A string α is lexicographically less than a string β (α<β ), if

1. α — is a prefix of β

or

String α=aca<β=acaaba , since it is a prefix of β.

String α=acaa<β=acab , since a

Formal languages

Definition: A language (Eng. language) over an alphabet Σ — a certain subset of Σ∗ . Such languages are sometimes called formal (Eng. formal) to emphasize the difference from language in the everyday sense.

Note that a language over Σ need not contain chains that include all symbols of Σ. Therefore, if it is known that L is a language over Σ, then it can be asserted that L — is a language over any alphabet that is a superset of Σ.

Operations on languages

Let L and M — be languages. Then the following operations can be defined on them.

1. Set-theoretic operations:
   • L∪M — union,
   • L∩ML — intersection,
   • L∖M — difference,
   • — complement.
2. Concatenation:
3. Concatenation with the reverse language: ; concatenation with the reverse word: .
4. Power of a language: .
5. Kleene closure: .
6. Homomorphism

Examples

• — the language consists of sequences of zeros, sequences of ones, and the empty string.
• — similar to the previous one, but does not contain the empty string.
• — contains all binary vectors and the empty string.
• If Lp — is the language of decimal representations of all prime numbers, then the language will contain the decimal representations of prime numbers that do not begin with a three.
• .

Homomorphism of languages

Definition: Let two alphabets Σ1,Σ2 be given. A homomorphism is a mapping such that:

• φ(ε)=ε , that is, it preserves the empty string
• , that is, it preserves concatenation

Definition:

Image of a language L⊂Σ∗1 under the homomorphism φ:Σ∗1→Σ∗2 (sometimes called a direct homomorphism) is the name given to the language

.
Note that φφ will be a homomorphism of the monoids ⟨L,⋅,ε⟩ and ⟨M,⋅,ε⟩

Definition: Preimage of a language M⊂Σ∗2M⊂Σ2∗ under the homomorphism φ:Σ∗1→Σ∗2 (sometimes called an inverse homomorphism) is the name given to the language
Note that φφ will be a homomorphism of the monoids ⟨L,⋅,ε⟩ and ⟨M,⋅,ε⟩

Examples

• trivial homomorphisms
  • the nulling one: φ(x)=ε,x∈L , then φ(L)={ε}
  • the identity one: φ(x)=x,x∈L , then φ(L)=L and φ−1(L)=L
• chain homomorphism — a function that substitutes some string for each symbol. More formally, for a given mapping a chain homomorphism is a function φ:Σ∗1→Σ∗2 , acting on each symbol of a string from the language as follows . Regular languages are closed under chain homomorphism
• the sunny language from children's games (where after every vowel in a word you must insert the letter "С" [s] followed by that same vowel) can be represented as a homomorphism of languages, where every consonant symbol maps to itself, and a vowel symbol z maps to zCz
• cyclic homomorphism: fix an order of the symbols in the alphabet, and map each symbol to the next one, with the last one mapped to the first. The inverse homomorphism will be the mapping of each symbol to the previous one.

Basic definitions. Simple combinatorial properties of words

• Basic definitions related to strings
• Period and border, their relationship
• The Fibonacci word
• The Thue-Morse word
• Lyndon decomposition
• The Landau-Schmidt algorithm
• The Crochemore algorithm
• The Main-Lorentz algorithm
• Manacher's algorithm
• Palindromic tree

String algorithms - Searching for a substring in a string

Exact search

• The naive algorithm for finding a substring in a string
• Finding a substring in a string using hashing. The Rabin-Karp algorithm
• Finding the longest common substring of two strings using hashing
• The prefix function
• The Knuth-Morris-Pratt algorithm
• The Knuth-Morris-Pratt automaton
• The Z-function
• Trie
• The Aho-Corasick algorithm
• Suffix automaton
• The Boyer-Moore algorithm
• The Apostolico-Crochemore algorithm
• The Colussi algorithm
• The Wright algorithm
• The Shift-And algorithm
• The two-way algorithm
• The Turbo Boyer-Moore algorithm

Fuzzy search

• The Landau-Vishkin algorithm (k mismatches)
• The Landau-Vishkin algorithm (k differences)

String algorithms - Suffix tree

• Suffix trie
• Compressed suffix tree
• Ukkonen's algorithm
• McCreight's algorithm
• Farach's algorithm

String algorithms - Suffix array

• Suffix array
• Building a suffix array using standard sorting methods
• The radix sort algorithm for suffixes of a cyclic string
• The Kasai et al. algorithm
• The Kärkkäinen-Sanders algorithm
• Algorithm for finding a substring in a string using a suffix array
• The number of sub-palindromes in a string

See also

• Period and border, their relationship
• The Fibonacci word
• The Thue-Morse word
• Regular languages: two definitions and their equivalence