Longest Common Prefix Array

Question

Following is the Suffix array and LCP array information for string MISSISSIPPI. I know that LCP gives information about the lenght of the longest common prefix between str[i - 1] and str[i]. How Do I get longest common prefix length between any two arbitrary suffixes of this string. For example, I want longest common prefix between MISSISSIPPI and ISSIPPI

SA  LCP
12  0     $
11  0     I$
8   1     IPPI$
5   1     ISSIPPI$
2   4     ISSISSIPPI$
1   0     MISSISSIPPI$
10  0     PI$
9   1     PPI$
7   0     SIPPI$
4   2     SISSIPPI$
6   1     SSIPPI$
3   3     SSISSIPPI$

Scratch

Answer 1

From http://en.wikipedia.org/wiki/Suffix_array, we have that "The fact that the minimum lcp value belonging to a consecutive set of sorted suffixes gives the longest common prefix among all of those suffixes can also be useful." So in your case, the LCP between MISSISSIPPI and ISSIPPI is min(4, 0) = 0.

You can find the minimum in a range in time O(1) via http://en.wikipedia.org/wiki/Range_Minimum_Query, and there is a lot of info on alternative approaches if you look at the TopCoder link there.

Rochelrochell

Thanks, What should be logic for following pairs (IPPI,MISSISSIPPI) or ( ISSIPPI, MISSISSIPPI ) – Scratch

For these two pairs - and for any pair that includes something < MISSISSIPPI and MISSISSIPPI - the element in the LCP range nearest MISSISSIPPI is 0, so the answer will be 0, regardless of what the other elements are. This reflects the fact that the prefix that sorts just before MISSISSIPPI is ISSISSIPPI, which does not match with a prefix of any non-zero length, so nothing which sorts < MISSISSIPPI can share a prefix with it either. – Rochelrochell

Answer 2

Longest Common Prefix on leetcode solved in dart language

class Solution {
    String longestCommonPrefix(List<String> strs) {
    if (strs.length == 0 || strs.isEmpty)
     {return '';}
    for (int i = 0; i < strs[0].length; i++) {
      String c = strs[0][i];
      for (int j = 1; j < strs.length; j++) {
        if (i == strs[j].length || strs[j][i] != c)
          return strs[0].substring(0, i);
      }
    }
    return strs[0];
  }
}

Laddie

Answer 3

Javascript Solution to the Longest Common Prefix Problem

const longestPrefix = arr => {
  if (arr.length === 0) {
    return "";
  }
  if (arr.length === 1) {
    return arr[0];
  }
  let end = 0;
  let check = false
  for (let j = 0; j < arr[0].length; j++){
    for (let i = 1; i < arr.length; i++) {
      if (arr[0][j] !== arr[i][j]) {
        check = true;
        break;
      }
    }
    if (check) {
      break;
    }
    end++;
  }
  return (arr[0].slice(0, end))
}

Test Input

console.log(longestPrefix(["Jabine", "Jabinder", "Jabbong"]))

Output

Jab

Paratroops