Question: given two strings, what can we say about their relationship?
In what follows, say our string lengths are m and n, with m ≤ n.
Just check each character against each other
If we're going to compare the same strings over and over, we can first hash them
Given two strings of equal length, we can count the number of characters at which they differ
More generally, just pad the smaller string at the end, say, so they're the same length.
We allow strings to change by
This is relevant in bioinformatics
Complexity O(mn)
Gives more weight to strings that match at the beginning
Contains all the suffixes of a given string
The nodes of the tree are all possible suffixes of a fixed string:
ex. DENIAL becomes a tree made up of
An edge of the tree corresponds to the possible endings of that node
ex. AABAAB will have an edge from AAB → AAB$ and one from AAB → AABA
But then we compress all of the chains
ex. since there's a single path AAB → AABA → AABAA → AABAAB, we compress this to AAB → AABAAB.
In implementation, you can just store the indices of a string, instead of repeatedly storing parts of the string.
Searching the tree is very convenient: