1

I have array:

let arr = ["logerror", "log:today", "log:1"]

I am looking for function how to get longest substring from this items.

Result:

log

Another example:

   let arr = ["dog+ěě+", "dog15qwqqq", "dogggggg"]

Result:

dog

Sure, I can write some algorithm, but is there any simple way?

How? Thanks

friageac
  • 29
  • 1
  • 3

5 Answers5

4

If you can phrase your question succinctly, you can often find what to search for. In this case, it looks like:

"Find the longest common substring from within an array of strings"

A quick google reveals an algorithm for finding the largest common substring between two strings:

https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Longest_common_substring

I don't want to copy the code as written there, as unsure of the copyright, but you could take the implementation and take something that will work with your array.

I would note that for large arrays, this may turn out to be a lengthy operation...

Paddy
  • 33,309
  • 15
  • 79
  • 114
2

I used a simple approach:

It sorts the array using sort() method.

Then, the most important step is to look just at the first and last items.

function commonSubsequence(array){
    let sortedArray = array.sort(); 
    let first = sortedArray[0];
    let last = sortedArray.pop();
    let length = first.length;
    let index = 0;
    
    while(index<length && first[index] === last[index])
        index++;
    return first.substring(0, index);
}
console.log(commonSubsequence(["logerror", "log:today", "log:1"]));
console.log(commonSubsequence(["dog+ěě+", "dog15qwqqq", "dogggggg"]));
Mihai Alexandru-Ionut
  • 47,092
  • 13
  • 101
  • 128
1

Here is my suggestion

function subStrArr(arr) {
  let chars = arr[0].split(""), sub = "";
  for (let i=0;i<chars.length;i++) {
    for (let j=1;j<arr.length;j++) {
      if (arr[j].indexOf(chars[i])==-1) return sub;
    }
    sub+=chars[i];
  }
}  

let arr1 = ["logerror", "log:today", "log:1"];
let arr2 = ["dog+ěě+", "dog15qwqqq", "dogggggg"];

console.log(subStrArr(arr1))
console.log(subStrArr(arr2))
mplungjan
  • 169,008
  • 28
  • 173
  • 236
  • Works fine in this particular case (common substring at the start of the string), but not for all cases. – sinisake Dec 19 '17 at 10:24
  • 2
    OP wanted from start - otherwise the algorithm is [MUCH more complex](https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Longest_common_substring#JavaScript) – mplungjan Dec 19 '17 at 10:26
  • 1
    Yep, just wanted to say the same (maybe i should rephrase my self) - code works if common substring is always at the start of the string. :) – sinisake Dec 19 '17 at 10:29
1

After some looking around I went for the string-algorithms npm package, which did the job nicely for me.

From the docs:

import { longestCommonSubstring } from 'string-algorithms';

const strings = [
  '12apple',
  '3apple4',
  'apple56'
];

console.log(longestCommonSubstring(strings));

produces the output apple.

Arnaud P
  • 12,022
  • 7
  • 56
  • 67
0

without DP approach

var lcs = function (n, m) {
    let lcs = 0 //to store longest common substring
    let s1 = n.length
    let s2 = m.length

    for(let i = 0;i < s1;i++){
        for(let j = 0; j< s2;j++){
            let track = 0
            //if letter are same, do while to check next letter
            if(n[i] == m[j]){
                while(i + track < s1 && j + track < s2 && n[i + track] == m[j + track]){
                    track += 1 // to track
                    if (lcs < track) {
                        lcs += 1
                    }
                }
            }
        }
    }

    return lcs;
};

var m = "abcdxyz"
var n = "xyzabcd" // 4

// var m = "dadef"
// var n = "adwce"//2

// var m = "acdghr";
// var n = "bgh"; //2

// var m = "A"
// var n = "A" //1
console.log(lcs(m, n));
DamarOwen
  • 147
  • 1
  • 5