Di antara algoritma pencarian pencocokan string, dua yang paling terkenal adalah algoritma KMP (Knuth-Morris-Pratt) dan algoritma BM (Boyer-Moore). Kedua algoritma memiliki waktu pencarian linier dalam kasus terburuk. Namun, dalam praktiknya, algoritme KMP tidak jauh lebih cepat dibandingkan fungsi pustaka C yang paling sederhana strstr(), sedangkan algoritme BM seringkali 3-5 kali lebih cepat dibandingkan algoritme KMP (tidak dipraktikkan secara pribadi). Namun algoritma BM belum menjadi algoritma yang tercepat. Berikut ini merupakan algoritma pencarian yaitu algoritma Sunday yang lebih cepat dibandingkan dengan algoritma BM.
Ide algoritma Sunday sangat mirip dengan ide karakter buruk pada algoritma BM. Satu-satunya perbedaan adalah bahwa setelah algoritma Sunday gagal mencocokkan, dibutuhkan karakter satu posisi di belakang bagian string target saat ini yang sesuai dengan string Pola untuk melakukan pencocokan karakter buruk. Ketika ditemukan bahwa pencocokan gagal, dinilai apakah karakter pada offset saat ini + Panjang string pola + 1 (diasumsikan sebagai posisi K) pada string induk ada di string Pola. Jika ada, sejajarkan posisinya dengan karakter pada string Pola, lalu cocokkan dari awal; jika tidak ada, pindahkan string Pola ke belakang, sejajarkan dengan karakter pada k+1 string induk, lalu cocok. Ulangi operasi di atas hingga ditemukan, atau string induk ditemukan. Saya menulis contoh kecil untuk mengimplementasikan algoritma berikut.
Dalam kode tersebut, dua algoritma pencocokan string diimplementasikan, satu adalah metode Minggu, dan yang lainnya adalah metode biasa yang memindahkan satu bit pada satu waktu. Perbandingan efisiensi keduanya ditunjukkan pada fungsi utama, keduanya pada tingkat nanodetik . Langkah-langkah rinci dari algoritma telah ditambahkan dengan komentar yang sesuai dalam kode. Mengenai algoritma BM, lain kali kita akan membandingkan dan menganalisis bersama ketika kosong.
Copy kode kodenya sebagai berikut:
impor java.util.HashMap;
impor java.util.LinkedList;
impor java.util.List;
import java.util.Map;
/**
* @penulis Scott
* @tanggal 28 Desember 2013
* @keterangan
*/
kelas publik SundySearch {
Teks string = nol;
Pola string = null;
int Pos saat ini = 0;
/**
* Daftar posisi karakter pertama dari substring yang cocok
*/
Daftar<Bilangan Bulat> matchedPosList = LinkedList baru<Bilangan Bulat>();
/**
* Peta karakter yang cocok, mencatat karakter mana yang ada dalam string yang cocok dan perpindahan terakhir setiap karakter
*/
Peta<Karakter, Integer> peta = HashMap baru<Karakter, Integer>();
public SundySearch(String teks, pola String) {
this.teks = teks;
this.pattern = pola;
ini.initMap();
};
/**
* Saat mencocokkan hari Minggu, digunakan untuk menyimpan posisi kemunculan terakhir setiap karakter dalam Pola, berurutan dari kiri ke kanan.
*/
kekosongan pribadi initMap() {
for (int i = 0; i < pola.panjang(); i++) {
this.map.put(pattern.charAt(i), i);
}
}
/**
* Pencocokan rekursif string biasa, jika pencocokan gagal, maju satu posisi
*/
Daftar publik<Bilangan Bulat> normalMatch() {
//Gagal mencocokkan, lanjutkan ke bawah
if (!matchFromSpecialPos(currentPos)) {
Pos saat ini += 1;
if ((teks.panjang() - Pos saat ini) < pola.panjang()) {
kembalikan MatchedPosList;
}
normalMatch();
} kalau tidak {
// Cocokkan dengan sukses, catat lokasi
matchedPosList.tambahkan(currentPos);
Pos saat ini += 1;
normalMatch();
}
kembalikan MatchedPosList;
}
/**
* Pencocokan hari Minggu, dengan asumsi posisi karakter K dalam Teks adalah: offset saat ini + Panjang string pola + 1
*/
Daftar publik<Integer> SundayMatch() {
// Jika tidak ada kecocokan yang berhasil
if (!matchFromSpecialPos(currentPos)) {
// Jika karakter K di Teks tidak muncul di string Pola, lewati seluruh panjang string Pola.
if ((Pos saat ini + pola.panjang() + 1) < teks.panjang()
&& !map.containsKey(text.charAt(currentPos + pattern.length() + 1))) {
currentPos += pola.panjang();
}kalau tidak {
// Jika karakter K pada Teks muncul pada string Pola, sejajarkan posisi karakter K pada Teks dengan posisi karakter K terakhir pada string Pola.
if ((Pos saat ini + pola.panjang() + 1) > teks.panjang()) {
Pos saat ini += 1;
} kalau tidak {
currentPos += pattern.length() - (Bilangan bulat) map.get(text.charAt(currentPos + pattern.length()));
}
}
// Saat pertandingan selesai, kembalikan perpindahan awal dari semua pertandingan yang berhasil.
if ((teks.panjang() - Pos saat ini) < pola.panjang()) {
kembalikan MatchedPosList;
}
mingguMatch();
}kalau tidak {
//Jika pencocokan berhasil, maju sedikit lalu cocokkan lagi
matchedPosList.tambahkan(currentPos);
Pos saat ini += 1;
mingguMatch();
}
kembalikan MatchedPosList;
}
/**
* Periksa apakah substring yang dimulai dari offset Teks yang ditentukan cocok dengan Pola
*/
boolean publik matchFromSpecialPos(int pos) {
if ((teks.panjang()-pos) < pola.panjang()) {
kembali salah;
}
for (int i = 0; i < pola.panjang(); i++) {
if (teks.charAt(pos + i) == pola.charAt(i)) {
if (i == (pola.panjang()-1)) {
kembali benar;
}
melanjutkan;
} kalau tidak {
merusak;
}
}
kembali salah;
}
public static void main(String[] args) {
SundySearch sundySearch = new SundySearch("halo ah Adolf adfsadfklf adf234masdfsdfdsfdsfdsffwerwrewrerwerwersdf2666sdflsdfk", "adf");
mulai panjang = System.nanoTime();
System.out.println("NormalMatch:" + sundySearch.normalMatch());
System.out.println("NormalMatch:" + (System.nanoTime() - mulai));
mulai = Sistem.nanoTime();
System.out.println("SundayMatch:" + sundySearch.sundayMatch());
System.out.println("SundayMatch:" + (System.nanoTime() - mulai));
}
}