Как найти самую длинную общую подстроку?

Question

[Сергей]

Есть две строки. Как, сопоставив их, выявить вхождение, присутствующее в обеих? Например:

const str1 = 'some/path/to/';
const str2 = '../to/my/file';
// Общая подстрока - '/to/'.

Comments

[alex4answ]

разбиваете по /, ищете общие в массивах

[Дмитрий Беляев]

а по какому принципу общей подстрокой не являются такие строки, как 'o', 'e', 't'?

[Сергей]

Дмитрий Беляев, поправил вопрос. В качестве результата берётся самая длинная найденная подстрока.

[Сергей]

alex4answ, а если общей частью будет 'path/to', склеивать обратно?

Answer 1

[Aetae]

На мелких строках конечно можно решать тупым перебором, но вообще это алгоритмическая задача:
https://en.wikipedia.org/wiki/Longest_common_subst...
https://en.wikibooks.org/wiki/Algorithm_Implementa...

Answer 2

[Дмитрий Беляев]

С учетом комментария

В качестве результата берётся самая длинная найденная подстрока

задачу можно решить такой функцией:

function findLongestMatchSubstring(str1, str2) {
  for(let len = str1.length; len--;) {
    for(let pos = 0; pos + len <= str1.length; pos++) {
      const substr = str1.slice(pos, pos + len);
      if(str2.includes(substr)) {
        return substr;
      }
    }
  }
}