CODEWITHSUNDEEP
javascriptstringlongest-substring
Alice
Alice

Reputation: 45

The longest repeating substrings JavaScript

I have a programm that can find the longest repeating substring of entered string, but the thing is, when there are 2 repeating substrings of the biggest length in answer I get only one of them.

For instance, for the string 123b456k123m456j the answer is 123, while answer 123 and 456 is expected..

Can I somehow fix this problem? If you know how, please answer my question))

let s = prompt('Enter string');

   
function substr(str, begin, end) {
  let result = "";
  for (let i = begin; i < end; i++) {
    result += str[i];
  }
  return result;
}

function lcp(str1, str2) {
  let n = Math.min(str1.length, str2.length);
  for (let i = 0; i < n; i++) {
    if (str1.charAt(i) != str2.charAt(i)) {
      return substr(str1, 0, i);
    }
  }
  return substr(str1, 0, n);
}

function lrs(str) {
  const suffixes = [];
  for (let i = 0; i < str.length; i++) {
    suffixes.push(substr(str, i, str.length));
  }
 
  suffixes.sort();
 
  let result = '';
  let res=[];
  for (let i = 0; i < str.length - 1; i++) {
    const p = lcp(suffixes[i], suffixes[i + 1]);
    if (p.length > result.length){
     result = p;
    }
  }
  return result;
}

alert(lrs(s));

Upvotes: 2

Views: 2338

Answers (2)

Robby Cornelissen
Robby Cornelissen

Reputation: 97130

Using String.prototype.match() and filtering out the shorter matches should get you there:

const lrs = (s) => s.match(/(.+)(?=.*\1)/g)
                    .filter((x, _, a) => !a.some((y) => x.length < y.length));

console.log(lrs('123b456k123m456j'));

The filter condition using Array.prototype.some() should be probably swapped out for something with better performance if you expect a large number of matches.

Update

As mentioned in the comments by @cars10m, this produces incorrect results in cases where part of a longer repeating pattern is already consumed by the regex matcher when it matched a shorter repeating pattern.

Solution is to wrap the entire expression into a look-ahead group and advance the regex matcher one character at a time:

const lrs = (s) => [...s.matchAll(/(?=(.+)(?=.*\1))./g)]
                   .map(([_,v]) => v)
                   .filter((x, _, a) => !a.some((y) => x.length < y.length));

console.log(lrs('123456k123m3456j'));

Upvotes: 4

Jithil P Ponnan
Jithil P Ponnan

Reputation: 1247

Try replacing your function Los with the below.

function lrs(str) {
const suffixes = [];
for (let i = 0; i < str.length; i++) {
    suffixes.push(substr(str, i, str.length));
}

suffixes.sort();

let result = [];
let res = [];
let lastLongestSubStrLen = 0;
for (let i = 0; i < str.length - 1; i++) {
    const p = lcp(suffixes[i], suffixes[i + 1]);
    if (lastLongestSubStrLen <= p.length) {
        result.push(p);
        lastLongestSubStrLen = p.length;
        continue;
    }
}
return result;

}

It will work! But, my concern here you have nested loops. We need to optimise that for performance.

Please note you need modify the if condition I just altered for error handling. Also, I didn't check the worst cases. For eg: the first occurrence of repeated substring is length of 2, and the next once is length of 3, then you might want to clear all the elements before pushing a new one.

Happy Coding!

Upvotes: 0

Related Questions