Самый длинный массив общих префиксов

Ниже приведена информация Suffix array и LCP array для строки MISSISSIPPI. Я знаю, что LCP дает информацию о длине самого длинного общего префикса между str[i - 1] и str[i]. Как получить самую длинную общую длину префикса между любыми двумя произвольными суффиксами этой строки. Например, мне нужен самый длинный общий префикс между MISSISSIPPI и 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$

algorithm string-matching data-structures
person Avinash    schedule 03.01.2012    source источник

Ответы (2)


arrow_upward
8
arrow_downward

Из http://en.wikipedia.org/wiki/Suffix_array мы получаем, что "Тот факт, что минимальное значение lcp принадлежность к последовательному набору отсортированных суффиксов дает самый длинный общий префикс среди всех этих суффиксов, также может быть полезным». Итак, в вашем случае LCP между МИССИСИППИ и ИССИПИ составляет мин (4, 0) = 0.

Вы можете найти минимум в диапазоне за время O(1) через http://en.wikipedia.org/wiki/Range_Minimum_Query, и есть много информации об альтернативных подходах, если вы посмотрите на ссылку TopCoder.

person mcdowella    schedule 03.01.2012
comment
Спасибо. Какой должна быть логика для следующих пар (IPPI, MISSISSIPPI) или (ISSIPPI, MISSISSIPPI) - person Avinash; 03.01.2012
comment
Для этих двух пар - и для любой пары, которая включает что-то ‹ MISSISSIPPI и MISSISSIPPI - ближайший к MISSISSIPPI элемент в диапазоне LCP равен 0, поэтому ответ будет 0, независимо от того, каковы другие элементы. Это отражает тот факт, что префикс, который сортируется непосредственно перед MISSISSIPPI, - это ISSISSIPPI, который не соответствует префиксу любой ненулевой длины, поэтому ничто, которое сортирует ‹ MISSISSIPPI, также не может использовать префикс с ним. - person mcdowella; 03.01.2012

arrow_upward
-1
arrow_downward

Javascript-решение проблемы с самым длинным общим префиксом

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))
}

Тестовый ввод

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

Вывод

Jab
person Community    schedule 30.08.2019