title: How to match and highlight all terms in any order from an array of strings?
body: <p>The requirements are:</p>
  <ul>
  <li>Find strings from an array (from here on called <em>options</em>) that include <strong>ALL</strong> the terms in <strong>ANY</strong> order</li>
  <li>Correctly highlight the matching terms - ie. insert a string before and after each matching term - I'm using <code>&lt;u&gt;</code> and <code>&lt;/u&gt;</code> here</li>
  <li>Both the search query and options can be &quot;anything&quot;</li>
  </ul>
  <p>For the sake of simplicity answers can concentrate on case-insensitive search through a list including only ASCII characters and assume that the term delimiter is a plain space - ie. a query entered as &quot;Foo bar baz&quot; means the search terms are <code>['foo', 'bar', 'baz']</code>.</p>
  <p>To clarify:</p>
  <ul>
  <li>All terms must exist separately from each other in matched options - ie. shorter terms should not exist only as substrings of longer terms and no two terms should overlap</li>
  <li>Repeated search terms must exist in the option at least as many times as in the query</li>
  </ul>
  <p>The final application is (perhaps not surprisingly) an autocomplete of sorts.</p>
  <blockquote>
  <h3>TL;DR</h3>
  <p>Most recent fiddle comparing the proposed algorithms side by side:<br>
  <a href="https://jsfiddle.net/Mikk3lRo/ndeuqn02/7/" rel="noreferrer">https://jsfiddle.net/Mikk3lRo/ndeuqn02/7/</a>
  <br>(feel free to update this link if you add a new algorithm)</p>
  <p>jsPerf comparing algorithms in a somewhat more realistic / representative way - a few strings are basically &quot;entered&quot; one character at a time on each rep:<br>
  <a href="https://jsperf.com/comparison-of-algorithms-to-search-and-highlight" rel="noreferrer">https://jsperf.com/comparison-of-algorithms-to-search-and-highlight</a></p>
  <p>At this point it is clear (thanks to trincot's excellent base-comparison) that the majority of time used by the original implementations was spent on DOM-output. Its significance has been minimized as much as possible in the fiddle.</p>
  <p>There is still a clear difference in performance between the algorithms in each search, but not one of them is consistently fast<em>est</em> on every keystroke. After revisiting and cleaning up my own &quot;Divide and Conquer&quot; it does outperform the others consistently in any realistic scenario I try though.</p>
  <p>Tigregalis introduced the idea of a pre-run optimization, which seems reasonable given that options are unlikely to change between keystrokes. I have added (a function for) this to all methods here. The only algorithm where I saw an obvious benefit from it was in Skirtle's Permutations, but I'll encourage each answerer to consider if it might be useful for their own algorithms.</p>
  <p>Some algorithms will be much easier to adapt than others. It is still my opinion that this will be more important than the minor performance differences in a real implementation.</p>
  <p>Note that the current version of Tigregalis' Shrinking Set has a bug - I've excluded it from fiddle and jsperf until that is fixed.</p>
  </blockquote>
  <hr />
  <h2>Viral Permutations</h2>
  <p>In theory this can be solved by &quot;manually&quot; constructing a RegExp that contains every possible permutation of the search terms separated by a capturing group to catch anything between terms - a search for &quot;foo bar&quot; results in <code>(foo)(.*?)(bar)|(bar)(.*?)(foo)</code>.</p>
  <p>The highlighting is then done in one pass with <code>string.replace()</code>. If there is any change in the string we have a match.</p>
  <p>Demo:</p>
  <p><div class="snippet" data-lang="js" data-hide="false" data-console="true" data-babel="false">
  <div class="snippet-code">
  <pre class="snippet-code-js lang-js prettyprint-override"><code>var options = ['United States', 'United Kingdom', 'Afghanistan', 'Aland Islands', 'Albania', 'Algeria', 'American Samoa', 'Andorra', 'Angola', 'Anguilla', 'Antarctica', 'Antigua and Barbuda', 'Argentina', 'Armenia', 'Aruba', 'Australia', 'Austria', 'Azerbaijan', 'Bahamas', 'Bahrain', 'Bangladesh', 'Barbados', 'Belarus', 'Belgium', 'Belize', 'Benin', 'Bermuda', 'Bhutan', 'Bolivia, Plurinational State of', 'Bonaire, Sint Eustatius and Saba', 'Bosnia and Herzegovina', 'Botswana', 'Bouvet Island', 'Brazil', 'British Indian Ocean Territory', 'Brunei Darussalam', 'Bulgaria', 'Burkina Faso', 'Burundi', 'Cambodia', 'Cameroon', 'Canada', 'Cape Verde', 'Cayman Islands', 'Central African Republic', 'Chad', 'Chile', 'China', 'Christmas Island', 'Cocos (Keeling) Islands', 'Colombia', 'Comoros', 'Congo', 'Congo, The Democratic Republic of The', 'Cook Islands', 'Costa Rica', 'Cote D\'ivoire', 'Croatia', 'Cuba', 'Curacao', 'Cyprus', 'Czech Republic', 'Denmark', 'Djibouti', 'Dominica', 'Dominican Republic', 'Ecuador', 'Egypt', 'El Salvador', 'Equatorial Guinea', 'Eritrea', 'Estonia', 'Ethiopia', 'Falkland Islands (Malvinas)', 'Faroe Islands', 'Fiji', 'Finland', 'France', 'French Guiana', 'French Polynesia', 'French Southern Territories', 'Gabon', 'Gambia', 'Georgia', 'Germany', 'Ghana', 'Gibraltar', 'Greece', 'Greenland', 'Grenada', 'Guadeloupe', 'Guam', 'Guatemala', 'Guernsey', 'Guinea', 'Guinea-bissau', 'Guyana', 'Haiti', 'Heard Island and Mcdonald Islands', 'Holy See (Vatican City State)', 'Honduras', 'Hong Kong', 'Hungary', 'Iceland', 'India', 'Indonesia', 'Iran, Islamic Republic of', 'Iraq', 'Ireland', 'Isle of Man', 'Israel', 'Italy', 'Jamaica', 'Japan', 'Jersey', 'Jordan', 'Kazakhstan', 'Kenya', 'Kiribati', 'Korea, Democratic People\'s Republic of', 'Korea, Republic of', 'Kuwait', 'Kyrgyzstan', 'Lao People\'s Democratic Republic', 'Latvia', 'Lebanon', 'Lesotho', 'Liberia', 'Libya', 'Liechtenstein', 'Lithuania', 'Luxembourg', 'Macao', 'Macedonia, The Former Yugoslav Republic of', 'Madagascar', 'Malawi', 'Malaysia', 'Maldives', 'Mali', 'Malta', 'Marshall Islands', 'Martinique', 'Mauritania', 'Mauritius', 'Mayotte', 'Mexico', 'Micronesia, Federated States of', 'Moldova, Republic of', 'Monaco', 'Mongolia', 'Montenegro', 'Montserrat', 'Morocco', 'Mozambique', 'Myanmar', 'Namibia', 'Nauru', 'Nepal', 'Netherlands', 'New Caledonia', 'New Zealand', 'Nicaragua', 'Niger', 'Nigeria', 'Niue', 'Norfolk Island', 'Northern Mariana Islands', 'Norway', 'Oman', 'Pakistan', 'Palau', 'Palestinian Territory, Occupied', 'Panama', 'Papua New Guinea', 'Paraguay', 'Peru', 'Philippines', 'Pitcairn', 'Poland', 'Portugal', 'Puerto Rico', 'Qatar', 'Reunion', 'Romania', 'Russian Federation', 'Rwanda', 'Saint Barthelemy', 'Saint Helena, Ascension and Tristan da Cunha', 'Saint Kitts and Nevis', 'Saint Lucia', 'Saint Martin (French part)', 'Saint Pierre and Miquelon', 'Saint Vincent and The Grenadines', 'Samoa', 'San Marino', 'Sao Tome and Principe', 'Saudi Arabia', 'Senegal', 'Serbia', 'Seychelles', 'Sierra Leone', 'Singapore', 'Sint Maarten (Dutch part)', 'Slovakia', 'Slovenia', 'Solomon Islands', 'Somalia', 'South Africa', 'South Georgia and The South Sandwich Islands', 'South Sudan', 'Spain', 'Sri Lanka', 'Sudan', 'Suriname', 'Svalbard and Jan Mayen', 'Swaziland', 'Sweden', 'Switzerland', 'Syrian Arab Republic', 'Taiwan, Province of China', 'Tajikistan', 'Tanzania, United Republic of', 'Thailand', 'Timor-leste', 'Togo', 'Tokelau', 'Tonga', 'Trinidad and Tobago', 'Tunisia', 'Turkey', 'Turkmenistan', 'Turks and Caicos Islands', 'Tuvalu', 'Uganda', 'Ukraine', 'United Arab Emirates', 'United Kingdom', 'United States', 'United States Minor Outlying Islands', 'Uruguay', 'Uzbekistan', 'Vanuatu', 'Venezuela, Bolivarian Republic of', 'Viet Nam', 'Virgin Islands, British', 'Virgin Islands, U.S.', 'Wallis and Futuna', 'Western Sahara', 'Yemen', 'Zambia', 'Zimbabwe'];
  var terms, terms_esc;
  function viral_permutations() {
      var t0, t1, i, permuted, res_elm, meta_elm, regex_string, regex, li, option, match_groups, highlighted;
      meta_elm = document.getElementById('viral_permutations_meta');
      res_elm = document.getElementById('viral_permutations_result');
      res_elm.innerHTML = meta_elm.innerHTML = '';
      
      t0 = performance.now();
      
      //Split query in terms at delimiter and lowercase them
      terms = document.getElementById('viral_permutations').value.split(/\s/).filter(function(n) {
          return n;
      }).map(function(term){
          return term.toLowerCase();
      });
      meta_elm.innerHTML += 'Terms: ' + JSON.stringify(terms) + '&lt;br&gt;';
          
      //Escape terms
      terms_esc = terms.map(function(term) {
          return term.replace(/[-[\]{}()*+?.,\\^$|#\s]/g, "\\$&amp;");
      });
      
      //Wrap terms in in individual capturing groups
      terms_esc = terms.map(function(term) {
          return '(' + term + ')';
      });
      
      //Find all permutations
      permuted = permutate_array(terms_esc);
      
      //Construct a group for each permutation
      match_groups = [];
      for (var i in permuted) {
          match_groups.push(permuted[i].join('(.*?)'));
      }
      
      try {
          //Construct the final regex
          regex_string = match_groups.join('|');
          //Display it
          document.getElementById('viral_permutations_regex').innerHTML = regex_string;
          meta_elm.innerHTML += 'RegExp length: ' + regex_string.length + '&lt;br&gt;';
          
          regex = new RegExp(regex_string, 'i');
      
  
          //Loop through each option
          for (i = 0; i &lt; options.length; i++) {
              option = options[i];
  
              //Replace the terms with highlighted terms
              highlighted = option.replace(regex, viral_permutations_replace);
  
              //If anything was changed (or the query is empty) we have a match
              if (highlighted !== option || terms.length === 0) {
                  //Append it to the result list
                  li = document.createElement('li');
                  li.innerHTML = highlighted;
                  res_elm.appendChild(li);
              }
          }
  
          //Print some meta
          t1 = performance.now();
          meta_elm.innerHTML += 'Time: ' + (Math.round((t1 - t0) * 100) / 100) + 'ms';
      } catch(e) {
          meta_elm.innerHTML += '&lt;span style="color:red"&gt;' + e.message + '&lt;/span&gt;';
      }
  }
  
  //The replacement function
  function viral_permutations_replace() {
      var i, m, j, retval, m_cased, unmatched;
      retval = '';
      
      //Make a clone of the terms array (that we can modify without destroying the original)
      unmatched = terms.slice(0);
      
      //Loop arguments between the first (which is the full match) and
      //the last 2 (which are the offset and the full option)
      for (i = 1; i &lt; arguments.length - 1; i++) {
          m = arguments[i];
          
          //Check that we have a string - most of the arguments will be undefined
          if (typeof m !== 'string') continue;
          
          //Lowercase the match
          m_cased = m.toLowerCase();
          
          //Append it to the return value - highlighted if it is among our terms
          j = unmatched.indexOf(m_cased);
          if (j &gt;= 0) {
              //Remove it from the unmatched terms array
              unmatched.splice(j, 1);
              retval += '&lt;u&gt;' + m + '&lt;/u&gt;';
          } else {
              retval += m;
          }
      }
      return retval;
  }
  
  //Helper function to return all possible permutations of an array
  function permutate_array(arr) {
      var perm, perm_intern;
      perm_intern = function(perm, pre, post, n) {
          var elem, i, j, ref, rest;
          if (n &gt; 0) {
              for (i = j = 0, ref = post.length; 0 &lt;= ref ? j &lt; ref : j &gt; ref; i = 0 &lt;= ref ? ++j : --j) {
                  rest = post.slice(0);
                  elem = rest.splice(i, 1);
                  perm_intern(perm, pre.concat(elem), rest, n - 1);
              }
          } else {
              perm.push(pre);
          }
      };
      perm = [];
      perm_intern(perm, [], arr, arr.length);
      return perm;
  }
  viral_permutations();</code></pre>
  <pre class="snippet-code-html lang-html prettyprint-override"><code>&lt;input type="text" id="viral_permutations" onkeyup="viral_permutations()"&gt;
  &lt;p id="viral_permutations_meta"&gt;&lt;/p&gt;
  &lt;pre style="width:100%;overflow:auto;background:#eee" id="viral_permutations_regex"&gt;&lt;/pre&gt;
  &lt;ul style="height:300px;overflow:auto" id="viral_permutations_result"&gt;&lt;/ul&gt;</code></pre>
  </div>
  </div>
  </p>
  <p><em>Thanks to trincot</em> for pointing out that my original version would occasionally highlight a recurring term twice - which is fixed in this snippet.</p>
  <p><strong>Fails because:</strong></p>
  <ul>
  <li>The regex grows exponentially as terms are added. At 7 terms (even single letters) it is past 250kb and my browser gives up with <code>Error: regexp too big</code>...</li>
  </ul>
  <hr />
  <h2>A few other noteworthy strategies that didn't work:</h2>
  <h3>Capturing groups with all terms in each group:</h3>
  <pre><code>(foo|bar)(.*)(foo|bar)
  </code></pre>
  <p><strong>Fails because:</strong></p>
  <ul>
  <li>Will match options that include repeated terms - fx. <code>The food in the food court</code> would match though it obviously shouldn't.</li>
  <li>If we &quot;double-check&quot; that all terms were, in fact, found it will fail to find valid matches - fx. <code>The food in the food bar</code> would find <code>foo</code> twice and never get to <code>bar</code>.</li>
  </ul>
  <h3>Negative lookaheads and backreferences:</h3>
  <pre><code>(foo|bar|baz)(.*?)((?!\1)(?:foo|bar|baz))(.*?)((?!\1|\3)(?:foo|bar|baz))
  </code></pre>
  <p><strong>Fails because:</strong></p>
  <ul>
  <li>Whenever terms are repeated in the query it will reach impossible conditions like &quot;Find me a <code>foo</code>, <code>bar</code> or <code>bar</code> which is not a <code>foo</code> nor a <code>bar</code>&quot;.</li>
  <li>I'm fairly certain it has other issues, but I stopped pursuing it when I realized it was logically flawed.</li>
  </ul>
  <h3>Positive lookaheads</h3>
  <pre><code>(?=.*foo)(?=.*bar)(?=.*baz)
  </code></pre>
  <p><strong>Fails because:</strong></p>
  <ul>
  <li>It is very difficult (if not impossible) to reliably highlight the found matches.</li>
  <li>I haven't found any way to ensure all terms actually exist - ie. they may all be individually present in the option, but shorter terms may only exist as substrings of longer terms - or terms may overlap.</li>
  </ul>