كيفية التحقق مما إذا كانت سلسلة تحتوي على سلسلة فرعية في جافاسكريبت؟

عادةً ما كنت أتوقع وجود طريقة String.contains()، لكن لا يبدو أن هناك واحدة.

ما هي طريقة معقولة للتحقق من هذا؟

الإجابة رقم 1

قدم ECMAScript 6 String.prototype.includes:

const string = "foo";
const substring = "oo";

console.log(string.includes(substring)); // true

String.prototype.includes حساس لحالة الأحرف (case-sensitive) وغير مدعوم من قبل إنترنت إكسبلورر (Internet Explorer) بدون إضافة بديلة (polyfill).

في بيئات ECMAScript 5 أو الأقدم، استخدم String.prototype.indexOf، والذي يُرجع -1 عندما لا يمكن العثور على جزء من السلسلة:

var string = "foo";
var substring = "oo";

console.log(string.indexOf(substring) !== -1); // true

الإجابة رقم 2

هناك String.prototype.includes في ES6:

"potato".includes("to");
> true

لاحظ أن هذا لا يعمل في Internet Explorer أو بعض المتصفحات القديمة الأخرى التي لا تدعم ES6 أو تدعمها بشكل غير كامل. لجعله يعمل في المتصفحات القديمة، قد ترغب في استخدام مترجم مثل Babel، أو مكتبة تحويل مثل es6-shim، أو هذا التعويض المساعد من MDN:

if (!String.prototype.includes) {
  String.prototype.includes = function(search, start) {
    'use strict';
    if (typeof start !== 'number') {
      start = 0;
    }

    if (start + search.length > this.length) {
      return false;
    } else {
      return this.indexOf(search, start) !== -1;
    }
  };
}

الإجابة رقم 3

بديل آخر هو KMP (كنوث-موريس-برات).

تبحث خوارزمية KMP عن سلسلة فرعية بطول m في سلسلة بطول n في أسوأ حالة في وقت O(n+m)، مقارنة بأسوأ حالة O(n⋅m) للخوارزمية البسيطة، لذلك قد يكون استخدام KMP معقولًا إذا كنت تهتم بتعقيد الوقت في أسوأ الحالات.

إليك تنفيذ بلغة جافاسكريبت من مشروع Nayuki، مأخوذ من https://www.nayuki.io/res/knuth-morris-pratt-string-matching/kmp-string-matcher.js:

// Searches for the given pattern string in the given text string using the Knuth-Morris-Pratt string matching algorithm.
// If the pattern is found, this returns the index of the start of the earliest match in 'text'. Otherwise -1 is returned.

function kmpSearch(pattern, text) {
  if (pattern.length == 0)
    return 0; // Immediate match

  // Compute longest suffix-prefix table
  var lsp = [0]; // Base case
  for (var i = 1; i < pattern.length; i++) {
    var j = lsp[i - 1]; // Start by assuming we're extending the previous LSP
    while (j > 0 && pattern[i] !== pattern[j])
      j = lsp[j - 1];
    if (pattern[i] === pattern[j])
      j++;
    lsp.push(j);
  }

  // Walk through text string
  var j = 0; // Number of chars matched in pattern
  for (var i = 0; i < text.length; i++) {
    while (j > 0 && text[i] != pattern[j])
      j = lsp[j - 1]; // Fall back in the pattern
    if (text[i]  == pattern[j]) {
      j++; // Next char matched, increment position
      if (j == pattern.length)
        return i - (j - 1);
    }
  }
  return -1; // Not found
}

console.log(kmpSearch('ays', 'haystack') != -1) // true
console.log(kmpSearch('asdf', 'haystack') != -1) // false