C# or JavaScript: Determining common prefix in strings

Question

Possible Duplicate:
Find common prefix of strings

Let's say I have an array of strings. The array has at least two elements, and possibly more. Each string in the array has at least two characters, and possibly more, and at least the first character of every string is the same.

Given said string array, what's the most efficient way to determine the longest prefix shared across all strings?

For example, given ['cowgirl', 'cowboy'], the common prefix is cow. Or, given ['a', 'abs', apples'], the common prefix is a.

Ted Hopp · Answer 1 · 2011-10-05T20:30:00.077

4

I think the simplest algorithm, and perhaps the most efficient, is to just examine the words in sequence, comparing the longest common prefix so far to each word to determine how much of it you can keep. Use the first string as the initial prefix.

EDIT: Here's some Javascript code that does the work:

function findLongestPrefix(list) {
    var prefix = list[0];
    var prefixLen = prefix.length;
    for (var i = 1; i < list.length && prefixLen > 0; i++) {
        var word = list[i];
        // The next line assumes 1st char of word and prefix always match.
        // Initialize matchLen to -1 to test entire word.
        var matchLen = 0;
        var maxMatchLen = Math.min(word.length, prefixLen);
        while (++matchLen < maxMatchLen) {
            if (word.charAt(matchLen) != prefix.charAt(matchLen)) {
                break;
            }
        }
        prefixLen = matchLen;
    }
    return prefix.substring(0, prefixLen);
}

edited Oct 05 '11 at 20:30

answered Oct 05 '11 at 05:38

Ted Hopp

232,168
48
399
521

1

Upvoted. You can eliminate the substring() call within the loop by storing the prefix length. – Fantius Oct 05 '11 at 19:47
Good point. I'll revise the code. – Ted Hopp Oct 05 '11 at 19:57
even after fixing the syntax errors this code doesn't work – Louis Ricci Oct 05 '11 at 19:59
@LastCoder I fixed the typos (sorry for the Java contamination). It works for me. Can you post a counterexample? Note that the code assumes that all elements of the list have at least the first character in common, as OP had specified and the comments make clear. – Ted Hopp Oct 05 '11 at 20:32
Seems to work fine now. Fyi: Flipped vote. – Louis Ricci Oct 06 '11 at 11:11

score -1 · Answer 2 · edited May 23 '17 at 11:47

-1

You can check these resources about finding the longest common prefix substring between two strings or more.. even if the Algorithms are presented in other languages I am sure you can adapt one to JavaScript.

Find common prefix of strings

Algorithm Implementation/Strings/Longest common substring

edited May 23 '17 at 11:47

Community

1
1

answered Oct 05 '11 at 04:39

Anas Karkoukli

1,342
8
13

-1: The link you mentioned is for longest common substring, a strictly harder problem. That leaves the duplicate link, which is more appropriate as a comment. – phooji Oct 05 '11 at 04:42

C# or JavaScript: Determining common prefix in strings

2 Answers2