Làm cách nào để kiểm tra xem một chuỗi có chứa chuỗi con từ một mảng javascript không?

Có hai cách phổ biến để kiểm tra xem một chuỗi có chứa chuỗi con hay không trong JavaScript. Cách hiện đại hơn là hàm String#includes()

Bạn có thể sử dụng String#includes() trong tất cả các trình duyệt hiện đại ngoại trừ Internet Explorer. Bạn cũng có thể sử dụng String#includes() trong Nút. js >= 4.0.0

Bảng tương thích từ Mozilla Developer Network

Nếu bạn cần hỗ trợ Internet Explorer, thay vào đó, bạn nên sử dụng phương pháp String#indexOf(), đây là một phần của JavaScript kể từ ES1 năm 1997

Nói chung, nếu bạn có bất kỳ nghi ngờ nào về việc liệu mã có chạy trong môi trường hỗ trợ includes() hay không, bạn nên sử dụng indexOf(). Cú pháp của hàm includes() chỉ ngắn gọn hơn một chút so với indexOf()

Cả String#includes() và String#indexOf() đều phân biệt chữ hoa chữ thường. Không chức năng nào hỗ trợ biểu thức chính quy. Để thực hiện tìm kiếm không phân biệt chữ hoa chữ thường, bạn có thể sử dụng biểu thức chính quy và hàm String#includes()1 hoặc bạn có thể chuyển đổi cả chuỗi và chuỗi con thành chữ thường bằng cách sử dụng hàm String#includes()2

Có thể có lúc bạn tìm kiếm một chức năng như String. Chứa(). Chà, không có tính năng như vậy trong JavaScript. Do đó, cách tốt nhất để đạt được điều này là gì?

EcmaScript-6

Nếu bạn đang sử dụng phiên bản JavaScript mới nhất, để phát triển, bạn có quyền tự do sử dụng chức năng bao gồm trong Nguyên mẫu chuỗi

ECMAScript 6 được giới thiệu

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

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

6

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

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

bao gồm thực hiện tìm kiếm phân biệt chữ hoa chữ thường trên chuỗi

Là nhà phát triển, bạn cần phải thận trọng khi bao gồm đang được sử dụng. Các trình duyệt cũ hơn và đặc biệt là Internet Explorer không hỗ trợ Chuỗi. nguyên mẫu. bao gồm. Điều này có nghĩa là bạn phải có cơ chế dự phòng trong mã của mình để xử lý các môi trường này

EcmaScript-5

indexOf có thể được sử dụng để quyết định xem chuỗi có chứa chuỗi con hay không. Phương thức indexOf sẽ trả về -1 nếu chuỗi con không có trong chuỗi. Nó thường được sử dụng trong mảng và có thể áp dụng tương tự với chuỗi

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

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

indexOf thực hiện tìm kiếm phân biệt chữ hoa chữ thường trên chuỗi

Thời gian phức tạp

Cho dù bạn sử dụng bao gồm hay indexOf — cả hai thuật toán ngây thơ đều có độ phức tạp về thời gian là O(m * n), trong đó m là độ dài của chuỗi cha và n là độ dài của chuỗi con

Nếu bạn đang hướng tới một giải pháp tốn ít thời gian phức tạp hơn, bạn cần sử dụng một thuật toán khác

Thuật toán Knuth-Morris-Pratt Bí danh thuật toán KMP-Thuật toán

Đầu tiên, thuật toán KMP có độ phức tạp về thời gian là O(m+n). Cái này nhanh hơn nhiều và tốt hơn cái ngây thơ

Thuật toán KMP thực hiện một cách tiếp cận tuyến tính để kiểm tra xem chuỗi con có trong chuỗi hay không. Đây là phiên bản Thuật toán KMP của tôi

function kmpSearch(pattern, text) {
  if (pattern.length == 0)
    return 0; // Immediate match
  var j = 0; // Number of chars matched in pattern
  for (var i = 0; i < text.length; i++) {
    if (text.charAt(i) != pattern.charAt(j)){
      j = 0; // Fall back in the pattern
    }
    if (text.charAt(i) == pattern.charAt(j)) {
      j++; // Next char matched, increment position
      if (j == pattern.length)
        return i - (j - 1);
    }
  }
  return -1; // Not found
}

Những gì chúng tôi làm ở trên là khá đơn giản. Hãy để chúng tôi giải mã thông qua dòng chảy, từng bước một

1. Nếu mẫu là một chuỗi rỗng, bạn có thể trả về true vì
2. Lặp qua chuỗi, từng ký tự
3. Nếu ký tự hiện tại trong văn bản không bằng ký tự hiện tại trong mẫu, hãy đặt lại con trỏ của mẫu về chỉ mục thứ 0
4. Tiếp tục lặp qua văn bản
5. Nếu ký tự hiện tại trong văn bản bằng với ký tự hiện tại trong mẫu, hãy tăng vị trí của ký tự hiện tại trong mẫu
6. Nếu độ dài của con trỏ, của mẫu khớp với độ dài của mẫu, hãy trả về chỉ số bắt đầu của mẫu trong văn bản
7. Nếu mẫu không bao giờ được tìm thấy, hãy trả về -1

Thuật toán KMP chắc chắn là giải pháp phù hợp với bạn, nếu bạn đang tìm kiếm một thuật toán tuyến tính để kiểm tra xem một chuỗi con có xuất hiện trong văn bản hay không

Sự kết luận

Bây giờ, chúng ta đã thành thạo cách kiểm tra xem một chuỗi con có tồn tại trong chuỗi hay không. Vì vậy, cho đến nay, đây là ba phương pháp thông thường và được sử dụng nhiều nhất để kiểm tra xem mẫu có được tìm thấy trong một chuỗi hay không. Tất nhiên, Thuật toán KMP không giới hạn ở JavaScript. Nó có thể được thực hiện trong bất kỳ ngôn ngữ lập trình nào. Và, đó là thuật toán tuyến tính của bạn để kiểm tra mẫu trong một chuỗi