Longest common prefix

Why this matters

A search box that completes what you type, a program that groups file paths by folder, and a tool that finds the shared start of several names all need the same answer. Given a list of words, which start do they all share, and how long is it?

The answer is called the longest common prefix. A prefix is the start of a string, such as fl at the start of flower. A prefix is common to a list of strings when every string begins with it. The longest common prefix is the longest such start.

This lesson gives two methods. The first starts with one word and cuts it down until every word starts with it. The second compares the words one position at a time, from left to right, and stops at the first position where they disagree. The code is C++ and uses std::string and std::vector.

Words for this lesson

A candidate is a prefix you are still testing. A column is one position in the strings, counted from 0. The first letter of each word is in column 0, the second letter is in column 1, and so on.

Every string has a length, which is the number of characters it holds. size() returns that number. An empty string has length 0, and it is a prefix of every string.

The idea with one example

Take three words: flower, flow and flight. Write them one under another, with each letter in its column.

column:  0 1 2 3 4 5
flower:  f l o w e r
flow:    f l o w
flight:  f l i g h t

The first two columns match in all three words, f and l. In column 2 the words disagree. flower and flow have o, but flight has i. The shared start is fl, which is 2 letters long.

Every method for this problem finds the same answer. The methods differ in how they search for it.

Method 1: Shorten one candidate

Start with the first word as your candidate. Check each word in turn. If a word does not start with the candidate, remove the last letter from the candidate and check again. When every word starts with the candidate, it is the answer.

Two facts make this work. The candidate only gets shorter, so it can never grow past the first word. And if a word starts with the candidate, then it also starts with every shorter piece of the candidate, so cutting from the end never removes a correct answer.

The C++ function starts_with checks whether a string begins with a given piece. It was added in C++20.

The output is:

input: "flower" "flow" "flight"
  shorten: "fl"
input: "dog" "racecar" "car"
  shorten: ""
input: "interview" "internet" "interval"
  shorten: "inter"

Walk through the first case by hand. The candidate starts as flower. The word flower starts with flower, so nothing changes. The word flow does not start with flower, so the candidate is cut to flowe, then to flow. Now flow starts with flow, so the loop moves on. The word flight does not start with flow, so the candidate is cut to flo, then to fl. flight starts with fl, so the answer is fl.

The second case shows the empty result. dog and car share no start, so the candidate is cut until it is empty. An empty string starts every word, so the loop ends with "".

Edge cases

Edge cases are the inputs that break a method if it is written carelessly. Here are four.

The output is:

input: "flow" "flower"
  shorten: "flow"
input: "alone"
  shorten: "alone"
input:
  shorten: ""
input: "" "a"
  shorten: ""

The empty list is handled by the first line of the function, before words.front() is called. front() on an empty vector reads a value that does not exist, which is undefined behaviour. The check must come first.

Method 2: Compare column by column

The second method looks at one column at a time. Take column 0 and check the letter in every word. If they all match, move to column 1. Stop at the first column where a word is too short or has a different letter. The answer is everything before that column.

The first word sets the letter to match. Each other word must have the same letter in that column, and must be long enough to have one.

The output is:

input: "flower" "flow" "flight"
  columns: "fl"
input: "dog" "racecar" "car"
  columns: ""
input: "interview" "internet" "interval"
  columns: "inter"
input: "flow" "flower"
  columns: "flow"
input: "alone"
  columns: "alone"
input:
  columns: ""
input: "" "a"
  columns: ""

Trace the third case. Columns 0 to 4 hold i, n, t, e and r in all three words. In column 5 the letters are v in interview, n in internet and v in interval. That column does not match, so the function returns the first 5 letters of interview, which is inter.

The inner loop checks every word before it moves to the next column. One mismatch in any word stops the search for all of them. The test col >= w.size() || w[col] != first[col] covers both ways a column can fail: the word is too short, or its letter is different.

Example 2: Strings that differ in case

Case matters in C++. Apple and apple do not share a prefix, because A and a are different characters.

The output is:

""
"Ap"

The first list has no common start, because Apple begins with an uppercase A and apple begins with a lowercase a. The second list shares Ap. If your input must ignore case, convert all the words to lowercase before you call either function.

Example 3: File paths in one folder

A common use is grouping file paths. Here the shared start can end in the middle of a name, and the program needs to cut it back to a whole folder.

The output is:

shared start: "/home/ana/photos/202"
shared folder: "/home/ana/photos/"

The shared start stops inside 202, because 2024 and 2023 differ in their last digit. A prefix search does not know about folders. The function rfind('/') returns the position of the last slash in the string. Adding 1 keeps that slash, so substr returns the whole folder part. If the shared start has no slash, rfind returns npos, and adding 1 wraps to 0. In that case the result is an empty string, which is correct when the paths share no folder.

Why each method finds the right answer

Method 1 keeps one rule. A cut only removes lengths that the current word cannot match. If a word does not start with the candidate, it cannot start with any longer candidate, because a longer candidate starts with the same letters. So no longer answer is ever lost. When the loop ends, every word starts with the candidate, and no longer prefix is possible, so the answer is the longest one.

Method 2 uses the same idea column by column. Suppose the first mismatch is in column k. Then at least one word differs from the first word in that column, so no prefix longer than k can be shared. Every column before k matched in all words, so the first k letters are shared. The answer is exactly those k letters.

Comparing the two methods

Both methods are correct. They do different amounts of work.

Here n is the number of words and m is the length of the shortest word, because the answer cannot be longer than the shortest word. The worst case for column comparison is a list of n identical words of length m, where the loop checks every letter of every word. The shorten method cuts the candidate at most as many times as the first word has letters, since the candidate only shrinks. Each cut is followed by a check that costs up to m letter comparisons.

For a short list the two methods run in about the same time. Column comparison stops as soon as it finds a mismatch, and it never looks past the first position where the words disagree. The shorten method is easy to read, and it is often the first thing people write.

Testing your code

Run every function on a small set of inputs whose answer you know. Include the cases where the method is most likely to fail. The table below lists a set that covers most of them.

Both functions should give the same answer for every row. If they differ, one of them has a bug.

Common mistakes

Calling front() on an empty list. Calling words.front() on an empty vector reads memory that is not part of the vector. The result is undefined. The first line of each function returns early for an empty list. Without that line, the program may print garbage or crash.

Forgetting the length check in column comparison. The test col >= w.size() comes before w[col]. If a word is shorter than the column, w[col] reads at or past its end. Reading more than one position past the end is undefined behaviour in C++. The check also gives the right answer. A word that ends before the column has no letter there, so the prefix must stop.

Cutting a UTF-8 string by bytes. Both methods work on bytes, and a byte is not always a whole character. The word café ends in é, which takes 2 bytes, and cafè ends in è, which also takes 2 bytes. The two words share their first 4 bytes: the letters c, a and f, and the first byte of the accented letter, which is 0xC3 in both. When I ran column_scan on "café" and "cafè", it returned caf followed by that single byte 0xC3. Many terminals show that byte as a box or a question mark, so the output looks like a broken letter. The fix is to step back to a character boundary. The fourth exercise asks you to write it.

Practice

Exercise 1: Trace the method

Use Method 1, shorten one candidate, on the list "prefix", "prelude", "presto". Write the candidate after each cut.

Show the answer

The candidate starts as prefix. It is cut to prefi, then pref, then pre. Both prelude and presto start with pre, so the answer is pre.

Exercise 2: Predict a short word

Predict the output of column_scan({"ab", "a"}) before you run it.

Show the answer

The answer is a. Column 0 has a in both words. In column 1, the word a is too short to have a letter, so the function returns the first 1 letter of ab, which is a.

Exercise 3: Explain the length check

In column_scan, the test is col >= w.size() || w[col] != first[col]. Why must col >= w.size() come first?

Show the answer

If col is at or past the end of w, the expression w[col] reads past the string. Because || stops at the first true part, placing the length test first means w[col] is never evaluated when the position is out of range. A word that ends early has no letter in that column, so the search must stop there.

Exercise 4: Stop at a character boundary

Write safe_prefix, which calls column_scan and then makes sure its result never ends in the middle of a UTF-8 character. Test it on "café" and "cafè", which should give caf, and on "café" and "cafê", which should give cafe.

Show the answer

After the prefix is found, step back while the next byte of the first word is a continuation byte. A continuation byte starts with the bits 10, so the test is (b & 0xC0) == 0x80.

#include <iostream>
#include <string>
#include <vector>
 
std::string column_scan(const std::vector<std::string>& words) {
    if (words.empty()) return "";
    const std::string& first = words.front();
    for (std::size_t col = 0; col < first.size(); ++col) {
        for (const std::string& w : words) {
            if (col >= w.size() || w[col] != first[col]) {
                return first.substr(0, col);
            }
        }
    }
    return first;
}
 
std::string safe_prefix(const std::vector<std::string>& words) {
    std::string p = column_scan(words);
    // Step back while the next byte of the first word is a continuation byte.
    while (!p.empty() && p.size() < words.front().size()
           && (static_cast<unsigned char>(words.front()[p.size()]) & 0xC0) == 0x80) {
        p.pop_back();
    }
    return p;
}
 
int main() {
    std::cout << "[" << safe_prefix({"café", "cafè"}) << "]\n";
    std::cout << "[" << safe_prefix({"café", "cafê"}) << "]\n";
}

Its output is:

[caf]
[cafe]

Exercise 5: Two strings only

Write a function common_start(a, b) that returns the shared start of two strings, using a single loop over the positions. Test it on "interval" and "internet", which should give inter.

Show the answer

Stop at the first position where the two strings differ, or where either string ends.

#include <iostream>
#include <string>
 
std::string common_start(const std::string& a, const std::string& b) {
    std::size_t i = 0;
    while (i < a.size() && i < b.size() && a[i] == b[i]) {
        ++i;
    }
    return a.substr(0, i);
}
 
int main() {
    std::cout << common_start("interval", "internet") << "\n";
}

The output is inter. The loop stops at position 5, where v and n differ.

Exercise 6: Work out the cost

A list has 50 words. The shortest word has 8 letters, and all 50 words are equal. About how many letter comparisons does Method 2 make in the worst case?

Show the answer

About 400. Each of the 8 columns is checked against all 50 words, so the count is 50 × 8 = 400. Column comparison stops early when words differ, so 400 is the most it can do.

Summary

• The longest common prefix is the longest start shared by every string in a list.
• Method 1 starts with the first word and cuts it until every word starts with it.
• Method 2 compares the words one column at a time and stops at the first mismatch.
• Both methods must handle an empty list and an empty word, and both check the length before reading a letter.
• Both methods work on bytes, so a UTF-8 result can end in the middle of a character unless you step back to a boundary.