How to determine if one string starts with what another ends with

Question

I have a list of phrases:

[
  "according to all known laws of aviation",
  "time flies when you're having fun..."
  ...
]

I would like to find all the phrases in this list that match with the end of an input string. For example:

getNext("did you know that time flies w")

should perform a search through the list to match any string that starts with what did you know that time flies w ends with. As an example, it should return a list that at least contains time flies when you're having fun since itends with time flies w which is the start of that phrase.

I can't think of any reasonable way to do this.

The only thing I can think of is running through each character in the input and check if it matches the start of the phrase. If it does, increment a counter. If it is >1 (or some other number) at the end of the loop, at the phrase to another list, along with the number of matches. From there I could sort the list to give the closest match first, and the less close ones last.

Surely there must be a better way to do this?

For a bit of background, you can see this Repl.it project and this very similar Python question.

Answer 1

If you JUST want to match the start of some array of strings, you can use a filter and a startsWith function pair.

  let test = "a ";
  const items = phrases.filter(phrase => phrase.startsWith(test));

NOTE IF you do not care and as your strings are all lower case use .toLowerCase() to make it match "I" and "i";

  let test = "a ";
  const items = phrases.filter(phrase => phrase.toLowerCase().startsWith(test));

Note: I edited this live example to show "contains" as well via a checkbox, just in case that helps illustrate an alternative.

Here is a live example:

let phrases = ["according to all known laws of aviation", "a blessing in disguise", "a bunch", "a dime a dozen", "beat around the bush", "better late than never", "bite the bullet", "break a leg", "call it a day", "cut somebody some slack", "cutting corners", "dead tired", "easy does it", "excuse me", "get it out of my system", "get it out of your system", "get out of hand", "get something out of my system", "get something out of your system", "get your act together", "give someone the benefit of the doubt", "go back to the drawing board", "good idea", "hang in there", "hit the nail on the head", "hit the sack", "how does that sound?", "i don't know", "i don't understand", "i love you", "i owe you one", "i'm fine", "i'm fine, thanks", "i'm really sorry", "i'm sorry", "it cost an arm and a leg", "it costs an arm and a leg", "it'll cost an arm and a leg", "it will cost an arm and a leg", "it's not rocket science", "i've never given it much thought", "kill two birds with one stone", "killing two birds with one stone", "let you off the hook", "let me off the hook", "look, it's", "make a long story short", "miss the boat", "never gonna give you up", "no pain,  no gain ", "on the ball ", "once upon a time ", "pull your leg ", "pulling your leg ", "pull yourself together ", "proof of concept ", "so far so good ", "so much ", "speak of the devil ", "thanks so much ", "thank you so much ", "that's the last straw ", "the best of both worlds ", "this is a test", "time flies when you're having fun", "to be honest", "to get bent out of shape", "to kill a mockingbird", "to make matters worse", "under the weather", "watch out", "we'll cross that bridge when we come to it ", "whatever floats your boat", "whatever you say ", "wrap your head around something", "you can say that again", "your guess is as good as mine", "there's no such thing as a free lunch", "throw caution to the wind", "you can't have your cake and eat it too ", "have your cake and eat it too", "judge a book by its cover ", "book by its cover", "last straw", "shut up", "be quiet", "how are you?", "never gonna give you up", "water under the bridge", "let you down", "birds and the bees", "pair of trainers", "i'd really like", "i wouldn't mind", "i could do with"];

$('#mywords').on('input change', function(event) {
  let grp = $("<div></div>");
  let test = $(this).val();
  $('#testing').html(test);
  const items = phrases.filter(phrase => phrase.startsWith(test));
  $.each(items, function(index, value) {
    let rowItem = $("<div class='row-item'></div>").text(index + ". " + value);
    grp.append(rowItem);
  });
  $('#results-list').html(grp.children());
});

function dochange(event) {
  let grp = $("<div></div>");
  let test = $('#mywords').val();
  $('#testing').html(test);
  let items = [];
  if (!$('#mywords-contain').prop('checked')) {
    items = phrases.filter(phrase => phrase.toLowerCase().startsWith(test));
  } else {
    items = phrases.filter(phrase => phrase.toLowerCase().includes(test));
  }
  $.each(items, function(index, value) {
    let rowItem = $("<div class='row-item'></div>").text(index + ". " + value);
    grp.append(rowItem);
  });
  $('#results-list').html(grp.children());
}

$('#mywords-contain').on('change', dochange);
$('#mywords').on('input change', dochange);

<script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/1.12.4/jquery.min.js"></script>
<label>Enter something:<input id="mywords" type="text"/></label><label>Check For contains:<input id="mywords-contain" type="checkbox"/></label><span id="testing">(empty)</span>
<div id="result-group">Result found:
  <div id="results-list"></div>
</div>

Answer 2

It is quite frustrated that I answer here, without anything better than the brute-force... I would really have enjoyed a more clever way to go through it, and still hope someone will.

But given your application, there a a few optimizations you must add on jojonas' algorithm. You are probably going to perform this check at each keystroke, and since it is an autocomplete, the input may grow in length pretty fast.

One first optimization is to cut the input to the length of the checked string. Given an input of length 8, and a string to compare of length 3, there is no way the first 5 iterations return a match

input:   "aaaaaaaa" (8)
compare:      "aaa" (3)
               ^- first possible match for compare.startsWith()

This can be quite easily done by initiating our iterator to max(input.length - compare.length, 0).

A second optimization to this algorithm consist in searching for the first index of the first letter of compare inside the remainder of input. No need to go through every characters, as long as it isn't the first one of compare we can be sure that compare.startsWith will return false. We can then repeat until we find which remainder is correct, once again removing quite a few loops in the whole process.

const phrases = ["according to all known laws of aviation", "a blessing in disguise", "a bunch", "a dime a dozen", "beat around the bush", "better late than never", "bite the bullet", "break a leg", "call it a day", "cut somebody some slack", "cutting corners", "dead tired", "easy does it", "excuse me", "get it out of my system", "get it out of your system", "get out of hand", "get something out of my system", "get something out of your system", "get your act together"];


inp.oninput = e => {
  const overlaps = getOverlaps(inp.value, phrases);
  makeList(overlaps);
  if(logged) console.clear();
};
let logged = false;
inp.oninput(); 
logged = true;

// "abcde", "def"
function getOverlaps(input, list) {
  return list.filter(compare => {
    // single logger, just for demo
    const log = (...args) => !logged && compare === "beat around the bush" && console.log.apply(console, args);

    // search only in possible area
    let i = Math.max(input.length - compare.length, 0); // 2
    
    log('initial i:', i);
    
    const first_letter = compare[0]; // "d"
    let remain = input.substr(i); // "cde"
    
    log('initial remain:', remain);
    
    while(i < input.length) {
      // jump to first letter
      let index = remain.indexOf(first_letter); // 1

      log('in-loop index:', index);

      if(index < 0) { // not found
        return false;
      }
      i += index; // 3
      remain = input.substr(i); // "de"
      
      log('in-loop remain:', remain);
      
      if(compare.startsWith(remain)) { // found
        return true; // =>
      }
      
      // wasn't this one, move by one char
      // (will jump to next occurence of first_letter) at next iteration
      i++;
      remain = input.substr(i);
    }
      
  });

}

function makeList(items) {
  list.innerHTML = '';
  items.forEach(e => 
    list.appendChild(
      document.createElement('li')
    ).textContent = e
  );
}

body{padding-bottom: 120px}

<input id="inp" value="according to all known laws of aviation to bring a beat a" autofocus>
<ul id="list"></ul>

Answer 3

I converted the answer from the Python question into Javascript after doing some research on the Python language:

function OverlapTest(input, compare) {
    for (var i = 0; i < input.length; i++) {
        if (compare.startsWith(input.substring(i))) {
            return true;
        }
    }

    return false;
}

This will return true if the strings overlap at the start and end and false if they don't.