Most efficient way to find the common prefix of many strings

Question

What is the most efficient way to find the common prefix of many strings.

For example:

For this set of strings

/home/texai/www/app/application/cron/logCron.log
/home/texai/www/app/application/jobs/logCron.log
/home/texai/www/app/var/log/application.log
/home/texai/www/app/public/imagick.log
/home/texai/www/app/public/status.log

I wanna get /home/texai/www/app/

I want to avoid char by char comparatives.

possible duplicate of [finding common prefix of array of strings](http://stackoverflow.com/questions/1336207/finding-common-prefix-of-array-of-strings) — Ja͢ck, Jun 18 '12 at 01:35

score 2 · Answer 1 · answered Jun 18 '12 at 01:32

You cannot avoid going through at least the common parts to find common prefix.

I don't think this needs any fancy algorithm. Just keep track of the current common prefix, then shorten the prefix by comparing the current prefix with the next string.

Since this is common prefix of all strings, you may end up with empty string (no common prefix).

Petar Ivanov · Answer 2 · 2012-06-18T01:39:45.700

I'm not sure what you mean by avoid char by char comparative, but you at least need to read the common prefix from each of the strings, so the following algorithm is the best you can achieve (just iterate over the strings until they deviate or until the current longest prefix count is reached):

List<string> list = new List<string>()
{
    "/home/texai/www/app/application/cron/logCron.log",
    "/home/texai/www/app/application/jobs/logCron.log",
    "/home/texai/www/app/var/log/application.log",
    "/home/texai/www/app/public/imagick.log",
    "/home/texai/www/app/public/status.log"
};

int maxPrefix = list[0].Length;
for(int i = 1; i < list.Count; i++)
{
    int pos = 0;
    for(; pos < maxPrefix && pos < list[i].Length && list[0][pos] == list[i][pos]; pos++);

    maxPrefix = pos;
}

//this is the common prefix
string prefix = list[0].Substring(0, maxPrefix);

Most efficient way to find the common prefix of many strings

2 Answers2