Petunjuk dan konteks
Ini adalah masalah pencocokan multi-pola untuk pemfilteran log, deteksi kata sensitif, atau penyorotan pada editor. Misalkan total panjang kata kunci adalah M dan panjang teks adalah N; laporkan setiap awal kecocokan dan ID kata kunci. Kamus bersifat tetap selama pra-pemrosesan, teks bisa sangat panjang, dan pewawancara mengharapkan pra-pemrosesan, kompleksitas pemindaian, dan penanganan tumpang tindih.
Apa yang dievaluasi pewawancara
Pewawancara ingin Anda memperluas pembagian prefiks trie menjadi sebuah finite-state machine. Jawaban yang kuat membangun failure link, mewarisi output di sepanjang failure link, dan menjelaskan mengapa setiap karakter menyebabkan transisi state yang terbatas. Jawaban yang lemah mengatakan "gunakan trie" tetapi tidak dapat menangani tumpang tindih sufiks atau fallback saat tidak cocok (mismatch).
Klarifikasi yang perlu ditanyakan terlebih dahulu
- Apakah pencocokan bersifat case-sensitive, dinormalisasi Unicode, atau berbasis byte? Definisi karakter mengubah trie dan unit posisi.
- Haruskah kecocokan yang tumpang tindih dan beberapa kata kunci yang berakhir pada satu posisi dikembalikan? Ini menentukan apakah rantai output lengkap atau tidak.
- Apakah kamus sering berubah? Kamus statis cocok untuk satu automaton; kamus dinamis mungkin memerlukan pembangunan ulang berversi.
- Apakah posisi dihitung dalam karakter, byte, atau unit kode UTF-16? Sesuaikan dengan kontrak pemanggil.
- Apakah teks tiba dalam bentuk chunk? Pemindaian lintas-chunk harus mempertahankan state alih-alih meresetnya pada setiap chunk.
Kerangka jawaban 30 detik
"Saya akan memasukkan setiap kata kunci ke dalam trie, lalu menggunakan BFS untuk membangun failure link untuk setiap node: sufiks terpanjang yang dapat digunakan setelah terjadi ketidakcocokan. Setiap node menggabungkan output terminalnya sendiri dengan output dari target kegagalannya. Selama pemindaian, ikuti transisi atau failure link dan pancarkan output node saat ini. Pra-pemrosesan bersifat linear terhadap total panjang kata kunci ditambah representasi edge; pemindaian adalah O(N + kecocokan), dan input berupa chunk hanya membutuhkan state automaton saat ini."
Jawaban mendalam langkah demi langkah
- Bangun trie. Setiap node menyimpan edge anak, failure link, dan ID kata kunci. Node terminal menambahkan ID; ia tidak boleh hanya menyimpan satu ID saja.
- Inisialisasi kegagalan. Anak langsung dari root gagal ke root. Proses node yang tersisa berdasarkan kedalaman menggunakan antrean (queue).
- Hitung transisi fallback. Untuk edge dari sebuah node, ikuti failure link induknya hingga edge karakter yang sama ditemukan; jika tidak, kembali ke root. Dengan demikian, pemindaian tidak pernah membandingkan ulang karakter teks sebelumnya.
- Agregasi output. Salin output dari target kegagalan atau simpan output link untuk menghindari penyalinan daftar; output link ditelusuri saat melaporkan kecocokan.
- Pindai teks. Coba edge anak untuk setiap karakter. Jika terjadi ketidakcocokan, ikuti failure link hingga edge atau root tercapai. Pancarkan setiap output pada node baru; posisi awal adalah indeks saat ini dikurangi panjang kata kunci ditambah satu.
- Tangani batas. Kata kunci yang tumpang tindih dipancarkan secara alami. Input yang terbagi dalam chunk membawa state antar chunk. Jika kecocokan sangat banyak, gunakan callback, batasan (cap), atau paginasi alih-alih menahan semua hasil O(kecocokan).
Gunakan hash map untuk alfabet umum dan array untuk alfabet tetap yang kecil jika memori memungkinkan. Untuk kamus yang berubah-ubah, bangun versi baru di latar belakang dan alihkan pembaca secara atomik sehingga pemindaian tidak pernah mengamati automaton parsial.
Contoh jawaban model
"Saya akan memasukkan semua kata kunci dan mencatat setiap ID terminal, kemudian membangun failure link dengan BFS. Anak root gagal ke root. Untuk edge lainnya, ikuti rantai kegagalan induk untuk menemukan transisi yang sama atau kembali ke root. Output mencakup ID terminal milik node itu sendiri dan output kegagalan, sehingga he dan she keduanya dipancarkan saat memindai she. Setiap karakter teks mengikuti transisi anak atau kegagalan, menghasilkan waktu pemindaian O(N + Z) di mana Z adalah jumlah kecocokan; pra-pemrosesan adalah O(M) ditambah penyimpanan edge. Teks berbentuk chunk mempertahankan state, dan pembaruan kamus membangun versi baru sebelum beralih."
Kesalahan umum
- Kesalahan: Memindahkan pointer dan teks ke belakang saat terjadi mismatch → Mengapa gagal: Ini berdegenerasi menjadi pemindaian ulang untuk setiap kata kunci → Perbaikan: Failure link menjaga indeks teks tetap monotonik.
- Kesalahan: Hanya menyimpan satu output per node → Mengapa gagal: Kata kunci sufiks dan endpoint bersama akan hilang → Perbaikan: Gabungkan output kegagalan atau pertahankan output link.
- Kesalahan: Mengklaim pemindaian selalu O(N) → Mengapa gagal: Melaporkan kecocokan itu sendiri dapat memakan biaya O(Z) → Perbaikan: Nyatakan O(N + Z) dan alirkan output secara streaming.
- Kesalahan: Mereset ke root di setiap chunk → Mengapa gagal: Kata kunci yang membentang antar-chunk tidak dapat cocok → Perbaikan: Bawa state automaton di antara chunk-chunk tersebut.
Pertanyaan lanjutan dan tanggapan
Mengapa tidak menjalankan KMP secara terpisah untuk setiap kata kunci?
Menjalankan KMP secara terpisah membutuhkan O(KN) pemindaian teks. Aho–Corasick berbagi prefiks trie dan memproses teks satu kali, yang cocok untuk kamus tetap dan teks panjang.
Mengapa failure link dapat menemukan setiap kecocokan?
Karena failure link menunjuk ke sufiks terpanjang yang dapat digunakan. Melanjutkan di sepanjang rantai kegagalan akan mengenumerasi setiap sufiks yang juga merupakan prefiks kata kunci, sehingga agregasi output menemukan kecocokan bersarang dan tumpang tindih.
Bagaimana jika hash map anak menghabiskan memori?
Pilih array untuk alfabet kecil, tabel edge yang kompak, atau double-array trie, dan gunakan output link untuk menghindari penyalinan daftar. Ukur jumlah node dan edge sebelum melakukan kompresi.
Bisakah kamus sering berubah?
Buat versi pada kamus, bangun automaton baru di latar belakang, validasi, dan ganti pointer pembaca secara atomik. Pertahankan versi lama secara singkat untuk stream yang sudah berlangsung.