Baru-baru ini saya menemukan tugas yang tidak terlalu sulit di LeetCode. Sebagai bagian dari tugas, saya harus menerapkan algoritme untuk mencari substring di dalam string. Saat mencoba menyelesaikan tugas, saya menyadari bahwa saya hanya tahu sedikit tentang cara mencari substring dan memutuskan untuk mempelajari topik ini lebih detail dan membagikan hasilnya kepada Anda .

Seperti yang dikatakan Wikipedia, “Menemukan substring adalah salah satu tugas pencarian informasi yang paling sederhana”, tetapi itu tidak sepenuhnya benar. Di bawah ini saya akan berbicara tentang berbagai algoritme untuk menyelesaikan masalah ini dan menunjukkan contoh implementasinya. Ayo mulai!

“Algoritma Brute Force” atau “Algoritma Pencarian Sederhana”

Algoritma brute force adalah algoritma sederhana untuk menemukan substring, yang terdiri dari iterasi berurutan pada semua karakter string dan mencari kecocokan dengan substring yang dicari. Jika tidak ditemukan kecocokan, algoritme menggeser substring yang dicari satu karakter ke kanan dan memulai pencarian lagi.

const strStr = (haystack, needle) => {
  const m = needle.length
  const n = haystack.length

  for (let windowStart = 0; windowStart <= n - m; windowStart++) {
    for (let i = 0; i < m; i++) {
      if (needle[i] !== haystack[windowStart + i]) {
        break
      }
      if (i === m - 1) {
        return windowStart
      }
    }
  }

  return -1
}

Fungsi pencarian terdiri dari sebuah loop terbatas pada n – m (panjang string pencarian – panjang string yang kita cari), yang memungkinkan kita untuk menghindari masalah jika string memiliki lebih sedikit karakter daripada pencarian string dan menghindari yang tidak perlu cek. Ini juga termasuk loop bersarang yang memiliki logika untuk membandingkan karakter.

Jika karakternya sama, kami terus membandingkan karakter dalam string dengan string pencarian hingga kami menemukan karakter yang tidak cocok. Setelah kami menemukannya, kami keluar dari loop bersarang dan mengulangi perbandingan lagi.

Pemeriksaan kedua dipicu jika kita mencapai akhir dan semua nilai cocok, maka kita mengembalikan indeks karakter pertama dari kata yang dicari dalam string. Jika tidak, kami mengembalikan -1, yang berarti string tidak ditemukan.

Manfaat menggunakan:

• Implementasi dan pemahaman yang sederhana
• Berfungsi untuk semua jenis data termasuk teks, numerik, dll.

Kerugian penggunaan:

• Performa buruk, terutama pada string besar dan saat mencari substring panjang
• Menggunakan banyak waktu dan memori.

“Algoritma Robin-Karp”

Algoritma Robin-Karp adalah salah satu algoritma pencarian yang efisien berdasarkan konsep hashing.

Algoritma bekerja sebagai berikut:

• Pertama, kami menghitung hash untuk jendela pertama string dan substring uji.
• Kemudian kami membandingkan hash secara berurutan. Jika hash cocok, perbandingan karakter demi karakter tambahan dilakukan. Jika kecocokan ditemukan, algoritma berhenti.
• Jika tidak ditemukan kecocokan, nilai hash untuk substring berikutnya dihitung dengan menggeser jendela satu karakter ke kanan dan menghitung nilai hash untuk substring baru.

const strStr = (haystack, needle) => {
  const haystackLen = haystack.length
  const needleLen = needle.length

  const prime = 101
  const d = 256

  let haystackHash = 0
  let needleHash = 0
  let fastHash = 1

  // loop 1
  for (let i = 0; i < needleLen - 1; i++) {
    fastHash = (fastHash * d) % prime
  }

  // loop 2
  for (let i = 0; i < needleLen; i++) {
    haystackHash = (d * haystackHash + haystack.charCodeAt(i)) % prime
    needleHash = (d * needleHash + needle.charCodeAt(i)) % prime
  }

  // loop 3
  for (let i = 0; i <= haystackLen - needleLen; i++) {
    if (needleHash === haystackHash) {
      let j

      for (j = 0; j < needleLen; j++) {
        if (haystack[i + j] !== needle[j]) {
          break
        }
      }

      if (j === needleLen) {
        return i
      }
    }

    if (i < haystackLen - needleLen) {
      haystackHash = (d * (haystackHash - haystack.charCodeAt(i) * fastHash) + haystack.charCodeAt(i + needleLen)) % prime
  
      if (haystackHash < 0) {
        haystackHash = (haystackHash + prime)
      }
    }
  }

  return -1
}

Sekarang izinkan saya memberi tahu Anda lebih banyak tentang fungsi pencarian.

Loop pertama digunakan untuk menghitung nilai yang digunakan untuk mempercepat perhitungan hash, bekerja sesuai dengan algoritma fastHash = d^(needleLen-1) % prime.

Loop ke-2 hanya menghitung hash dari string dan substring.

Di loop ke-3, pencarian kecocokan terjadi. Jika nilai hash cocok, kami memeriksanya satu per satu. Jika terjadi ketidakcocokan, kami keluar dari loop dan mengulangi pencarian kecocokan. Jika semua karakter cocok, maka kami hanya mengembalikan indeks elemen pertama.

Jika nilai hash tidak cocok, kami menghitung nilai hash jendela baru untuk perbandingan berikutnya dan mengulangi pencarian kecocokan.

Keuntungan menggunakan metode ini:

• Pencarian cepat untuk substring dalam kasus rata-rata, terutama untuk string dan substring yang panjang;
• Kemampuan untuk secara efisien mencari beberapa substring sekaligus menggunakan kode hash yang sama untuk semua substring yang diinginkan;
• Hashing memungkinkan Anda melewati banyak substring yang tidak sesuai, sehingga mengurangi jumlah perbandingan yang diperlukan.

Kerugian menggunakan metode ini:

• Dalam beberapa kasus, misalnya, saat menggunakan fungsi hash sederhana, kecocokan palsu dimungkinkan, yang juga harus diperiksa karakter demi karakter;
• Kebutuhan untuk memilih fungsi hash yang efisien yang tidak hanya menghitung nilai hash dengan cepat, tetapi juga mendistribusikannya secara merata di antara semua kemungkinan nilai;
• Jika nilai hash terlalu kecil atau terlalu besar ditemui, mungkin ada masalah luapan yang perlu ditangani.

Anda dapat mengetahui lebih lanjut di sini: wikipedia.org

Algoritma Knuth-Morris-Pratt (KMP).

Saat ini algoritma ini dianggap paling cepat, karena berjalan dalam waktu linier. Ini berguna saat mencari data dalam jumlah besar. Selain itu, saya menemukan bahwa algoritme ini digunakan tidak hanya untuk pencarian substring, tetapi juga di:

• Cari gen dalam urutan DNA;
• Pelengkapan otomatis di mesin telusur;
• Pengenalan sinyal dalam pemrosesan sinyal digital.

Sekarang mari beralih ke algoritme itu sendiri. Algoritma KMP membangun tabel prefiks (yang merupakan bagian utama dari algoritme) untuk substring dan menggunakannya untuk menentukan posisi terbaik untuk melanjutkan pencarian saat karakter tidak cocok.

Tabel awalan berisi informasi tentang awalan terbesar yang juga merupakan akhiran (yaitu substring yang dimulai pada awal string) dari elemen ini.

Berikut adalah contoh penerapan fungsi awalan:

const prefix = (str) => {
  const n = str.length
  const p = Array(n).fill(0)

  let i = 1, j = 0

  while (i < str.length) {
    if (str[i] === str[j]) {
      p[i] = j + 1
      i ++
      j ++
    } else {
      if (j === 0) {
        p[i] = 0
        i ++
      } else {
        j = p[j - 1]
      }
    }
  }

  return p
}

Contoh: untuk string “abcabcd”, fungsi awalan akan terlihat seperti ini:
[0, 0, 0, 1, 2, 3, 0], di mana tiga elemen pertama adalah 0 karena tidak ada awalan yang merupakan sufiks dari tiga karakter pertama; 1, 2 dan 3 karena “a”, “ab” dan “abc” adalah awalan yang juga merupakan akhiran; dan terakhir, elemen terakhir adalah 0 karena “abcabc” adalah awalan dari string “abcabcd” tetapi bukan akhiran dari elemen terakhir “d”.

Setelah menerapkan fungsi awalan, kita dapat beralih ke penerapan algoritme pencarian. Inti dari algoritme adalah membandingkan karakter string dan substring, dan jika karakter tidak sama, kami mengambil nilai dari tabel awalan dan menggunakannya sebagai indeks untuk transisi, sehingga memungkinkan kami untuk melewati a beberapa karakter dan menemukan substring yang diinginkan lebih cepat.

const findStr = (str, searchString) => {
  const searchStringPrefix = prefix(searchString)
  let i = 0, j = 0

  while (i < str.length) {
    if (str[i] === searchString[j]) {
      j ++
      i ++

      if (j === searchString.length) {
        return i - searchString.length
      }
    } else {
      if (j > 0) {
        j = searchStringPrefix[j - 1]
      } else {
        i ++
      }
    }
  }

  if (i === str.length && j !== searchString.length) {
    return -1
  }
}

Keuntungan menggunakan algoritma KMP:

• Kompleksitas waktu linier: O(n+m)di mana n adalah panjang string dan m adalah panjang substring.
• Secara efisien menangani teks besar dengan beberapa kemunculan substring.

Kerugian menggunakan algoritma KMP:

• Membutuhkan tabel awalan yang telah ditentukan sebelumnya, yang dapat diambil O(m) waktu dan O(m) Penyimpanan.
• Bisa jadi sulit untuk dipahami dan diimplementasikan, terutama untuk pemula pemrograman.

Saya juga ingin mencatat bahwa KMP hanya memberikan peningkatan kinerja jika ada nilai positif dalam larik awalan. Hanya dengan begitu penunjuk akan digeser lebih dari satu. Tetapi bahkan dalam kasus “semua nol” dalam larik, pencarian bekerja dengan cukup baik.