CODEWITHSUNDEEP
algorithmdata-structuresstring-matching
Avinash
Avinash

Reputation: 13257

Longest Common Prefix Array

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$

Upvotes: 8

Views: 7405

Answers (3)

Shahoriar Nahid
Shahoriar Nahid

Reputation: 162

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];
  }
}

Upvotes: 0

user6184932
user6184932

Reputation:

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

Upvotes: -1

mcdowella
mcdowella

Reputation: 19601

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.

Upvotes: 9

Related Questions