prefix, suffix and substring

These three words name the natural ways one string can sit inside another, like spotting a smaller word hidden in a bigger one. A prefix is a chunk taken from the front, a suffix is a chunk taken from the back, and a substring is any contiguous chunk taken from somewhere in the middle (or front, or back). In the word concatenation, con is a prefix, tion is a suffix, and caten is a substring.

Precisely, a string p is a prefix of w if w can be written as p followed by something, that is w = p y for some string y. A string s is a suffix of w if w = x s for some string x. And a string u is a substring (sometimes called a factor) of w if w = x u y for some strings x and y, meaning u appears as a block of consecutive symbols inside w. The empty string ε is a prefix, a suffix, and a substring of every string, and the whole string w is a prefix, suffix, and substring of itself. Note the word contiguous: in abc, the symbols a and c together are not a substring, because they are not next to each other. Picking out non-adjacent symbols gives a subsequence, which is a different idea.

These notions appear constantly. Pattern matching and search are about finding a substring; many language definitions are phrased as no string in L has such-and-such a prefix; and parsing reads a prefix of the input at a time. Keeping prefix, suffix, and substring straight is small but pays off whenever a problem says something about where a pattern can occur in a string.