What is a string?

• In math: A string is a finite sequence of symbols that are chosen from a set called an alphabet.

• In CS: A string is a sequence of characters.

Strings in the way computers represent textual information.

Classes of problems on strings

Most problems with strings have to do with search a string or a list of strings/patterns in another string.

• String representation: How can we represent text in computer memory?
• String search: Given a string, how can we find all occurences of it in another string?
• Regular expressions: Given a pattern, how can we find all its occurences in a string?
• Approximate matching: How similar are two strings?
• Edit script: What is the minimal set of additions/deletions to go from one string to another?

String representation

Encodings

In computer memory, strings are nothing more that binary data.

Data in computer memory

In order to interprect what the value 0x48 (first 8 bits) means in terms of characters, we need an encoding.

The problem of encoding predates computers. For example, Morse code is an encoding between short and long sounds to Latin script.