CODEWITHSUNDEEP
javascriptnode.jslongest-substring
1641_Shourav Chy
1641_Shourav Chy

Reputation: 49

Longest commong Substring from multiple strings

    let lcs = (s, t) => {
        let dp = Array.from({ length: s.length + 1 }, () => Array.from({ length: t.length + 1      }, () => 0));
        let maxLen = 0, endIndexS = 0, endIndexT = 0;

        for (let i = 1; i <= s.length; i++) {
            for (let j = 1; j <= t.length; j++) {
                if (s[i - 1] === t[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    if (dp[i][j] > maxLen) {
                        maxLen = dp[i][j];
                        endIndexS = i;
                        endIndexT = j;
                    }
                }
            }
        }

        if (maxLen === 0) return ''; // If no common subsequence found

        return s.substring(endIndexS - maxLen, endIndexS);
    };

    let args = process.argv.slice(2);
    if (args.length === 0) {
        console.log('');
    } else {
        let result = args[0];
        for (let i = 1; i < args.length; i++) {
            result = lcs(result, args[i]);
            if (result === '') break;
        }
        console.log(result);
    }

I have written the above code where i had to take input from terminal and print the longest substring..it's working for some test cases ..But the test cases like this : ZZZABXXX XXXYYYAB ABYYYZZZ is not working as it's suppose to output AB it's returning empty string..

Upvotes: 1

Views: 88

Answers (1)

Alexander Nenashev
Alexander Nenashev

Reputation: 23957

Your logic is wrong, you find ZZZ for the first pair, and then there's no match further.

Merge suffix trees of the strings with common nodes and find the longest path containing all the strings.

More efficient algorithms exist to build a suffix tree/array and find the longest common substring. Just investigate.

function lcs(strings){
  const tree = {};
  let n = 0, result = '';
  for(const str of strings){
    for(let i=0;i<str.length;i++){
      let node = tree;
      let r = '';
      for(const c of str.slice(i)){
        r += c;
        if(n) {
          if((node = node[c])?.strings.size !== n) break; // prematurely stop if no match with previous strings
        } else (node = node[c] ??= {strings:new Set});
        node.strings.add(str);
        if(node.strings.size === strings.length && r.length > result.length) result = r;
      }
    }
    n++;
  }
  
  return result;
}

console.log(lcs('ZZZABXXX XXXYYYAB ABYYYZZZ'.split(' ')));
console.log(lcs('ZZZABXXX XXXYYYAB ABYYYZZZXXX'.split(' ')));
.as-console-wrapper{
max-height: 100% !important;
}

Upvotes: 1

Related Questions