Как определить, начинается ли одна строка с того, чем заканчивается другая

Question

У меня есть список фраз:

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

Я хотел бы найти все фразы в этом списке, которые соответствуют концу входной строки.Например:

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

должен выполнить поиск в списке, чтобы найти любую строку, которая начинается с того, чем заканчивается did you know that time flies w.В качестве примера, он должен вернуть список, который по крайней мере содержит time flies when you're having fun, поскольку он начинается с time flies w, который является началом этой фразы.

Я не могу придумать никакого разумного способа сделать это.

Единственное, о чем я могу думать, - это бегать по каждому символу на входе и проверять, соответствует ли он началу фразы.Если это так, увеличьте счетчик.Если это> 1 (или другое число) в конце цикла, в фразе другого списка вместе с количеством совпадений.Оттуда я мог бы отсортировать список, чтобы сначала дать самое близкое совпадение, а последнее - менее близкое.

Конечно, должен быть лучший способ сделать это?

Для некоторого фона,вы можете увидеть этот проект Repl.it и этот очень похожий вопрос по Python .

Answer 1

Если вы просто хотите сопоставить начало некоторого массива строк, вы можете использовать функциональную пару filter и startsWith.

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

ПРИМЕЧАНИЕ ЕСЛИ вам все равновсе строки в нижнем регистре используют .toLowerCase(), чтобы они соответствовали "I" и "i";

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

Примечание: я отредактировал этот живой пример, чтобы показывать также "содержит" через флажок, просто вслучай, который помогает проиллюстрировать альтернативу.

Вот живой пример:

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

Я очень расстроен, что я отвечаю здесь, без чего-либо лучшего, чем грубая сила ... Я действительно наслаждался бы более умным способом пройти через это, и все еще надеюсь, что кто-то сделает это.

Ноучитывая ваше приложение, есть несколько оптимизаций, которые вы должны добавить в алгоритм jojonas.Вы, вероятно, будете выполнять эту проверку при каждом нажатии клавиши, и, поскольку это автозаполнение, длина ввода может увеличиваться довольно быстро.

Одна из первых оптимизаций заключается в том, чтобы сократить ввод до длины проверяемой строки.Учитывая ввод длины 8 и строку для сравнения длины 3, невозможно, чтобы первые 5 итераций возвращали совпадение

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

. Это можно сделать довольно просто, инициировав наш итератор в max(input.length - compare.length, 0).

Вторая оптимизация этого алгоритма состоит в поиске первого индекса первой буквы compare внутри оставшейся части input.Не нужно проходить через все символы, если это не первый из compare, мы можем быть уверены, что compare.startsWith вернет false.Затем мы можем повторять до тех пор, пока не найдем, какой остаток является правильным, еще раз удалив немало петель во всем процессе.

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

Я преобразовал ответ из вопроса о Python в Javascript после некоторого исследования языка Python:

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

    return false;
}

Это вернет true, если строки перекрываются в начале и конце и falseесли они этого не сделают.