Wawancara coding: bagaimana cara mengimplementasikan suffix automaton dan menjelaskan clone state?

Pertanyaan

Diberikan sebuah string s, bangun suffix automaton (SAM) secara online. Implementasikan extend(c), jelaskan len, link, transisi, dan endpos, serta gunakan struktur tersebut untuk menghitung substring berbeda, menghitung kemunculan pola, atau menemukan longest common substring. Jelaskan mengapa jumlah state adalah O(n) dan kapan clone diperlukan.

Yang diuji oleh pewawancara

• Apakah Anda dapat mendeskripsikan sebuah state sebagai kelas ekuivalensi endpos alih-alih sekadar simpul trie biasa.
• Apakah Anda membedakan cabang direct-link, root-link, dan clone selama konstruksi.
• Apakah Anda mempertahankan len[link[v]] < len[v], transisi deterministik, dan invarian pohon suffix-link.
• Apakah Anda dapat mengubah invarian struktural menjadi hasil kueri dan kompleksitas.

Jawaban model

SAM adalah DFA parsial minimal yang mengenali setiap substring dari string sumber. State v menyimpan panjang maksimum yang direpresentasikan len[v]; link[v] menunjuk ke sufiks terpanjang di kelas ekuivalensi lain. State tersebut merepresentasikan interval berurutan (len[link[v]], len[v]], sehingga satu state dapat mewakili beberapa panjang substring.

Ketika sebuah karakter ditambahkan, buat cur dan telusuri suffix link, menambahkan transisi yang hilang. Jika target yang ada q memenuhi len[p]+1 == len[q], hubungkan cur langsung ke q. Jika tidak, salin q ke dalam sebuah clone dengan len = len[p]+1, alihkan transisi yang relevan pada jalur suffix-link, dan arahkan baik link[q] maupun link[cur] ke clone tersebut. Clone ini memulihkan invarian panjang berurutan.

Setiap state non-root menyumbang len[v] - len[link[v]] substring berbeda. Untuk menghitung kemunculan, inisialisasi satu untuk state yang sesuai dengan prefiks sumber, lalu sebarkan hitungan ke suffix link dalam urutan len yang menurun.

Sketsa implementasi

Pseudokode di bawah ini menunjukkan konstruksinya; transisi dapat menggunakan hash map atau ordered map.

extend(c):
  cur = new state
  len[cur] = len[last] + 1
  p = last
  while p != -1 and c not in next[p]:
    next[p][c] = cur
    p = link[p]
  if p == -1:
    link[cur] = root
  else:
    q = next[p][c]
    if len[p] + 1 == len[q]:
      link[cur] = q
    else:
      clone = copy(q)
      len[clone] = len[p] + 1
      while p != -1 and next[p][c] == q:
        next[p][c] = clone
        p = link[p]
      link[q] = link[cur] = clone
  last = cur

Jumlahkan len[v] - len[link[v]] di seluruh state non-root untuk mendapatkan jumlah substring berbeda. Untuk hitungan kemunculan, ikuti transisi ke state pola dan baca hitungan yang disebarkan dalam urutan panjang menurun.

Jebakan umum

• Memperlakukan SAM sebagai trie yang hanya menerima sufiks, alih-alih sebuah kompresi dari semua kelas endpos.
• Menyalin transisi clone tetapi membiarkan link-nya tidak konsisten, yang merusak interval panjang berikutnya.
• Mengalihkan terlalu sedikit transisi karena penelusuran suffix-link berhenti sebelum state pertama yang tidak lagi menunjuk ke q.
• Menghitung setiap clone sebagai kemunculan prefiks sumber, yang membuat semua hitungan kemunculan menjadi berlebih.
• Menggunakan array transisi berukuran tetap untuk alfabet besar tanpa menyatakan asumsi memori dan pengkodeannya.

Pertimbangan kompleksitas

Dengan alfabet tetap atau transisi berbasis hash, konstruksi membutuhkan waktu dan ruang O(n), dengan paling banyak sekitar 2n-1 state. Map transisi terurut menambahkan faktor yang terkait dengan operasi alfabet. SAM sangat cocok untuk banyak kueri substring pada satu teks tetap; suffix array dapat lebih mudah dikendalikan untuk penelusuran leksikografis, pekerjaan LCP, dan lokalitas cache.

Batasan linear mengasumsikan penambahan online di akhir. Menyisipkan atau menghapus di tengah, atau memperbarui kedua ujungnya, memerlukan struktur yang berbeda; extend tidak dapat begitu saja digunakan kembali sambil mempertahankan invarian miliknya.

Mulailah dengan string kosong, satu karakter, karakter berulang, dan input pemicu clone seperti abbb. Kemudian bandingkan string acak terhadap himpunan brute-force untuk jumlah substring berbeda dan hitungan kemunculan. Untuk longest common substring, alirkan string kedua melalui SAM dan ikuti suffix link saat terjadi ketidakcocokan.

Referensi

• Catatan SAM CP-algorithms: interval state, konstruksi clone, dan rumus kueri.
• Makalah smallest-substring-automaton oleh Blumer et al.: batasan teoretis state dan transisi.
• Catatan algoritma string Carnegie Mellon: kapan suffix array dan suffix automata lebih disukai.

Pertanyaan lanjutan

Mengapa setiap state merepresentasikan interval panjang yang berurutan?

Substring dalam satu kelas endpos membentuk urutan panjang tanpa celah. Suffix link mengidentifikasi kelas batas yang memuat sufiks sejati terpanjang, sehingga intervalnya tepat berupa (len[link[v]], len[v]].

Kapan clone diperlukan?

Jika target yang ada q memiliki len[q] > len[p]+1, target tersebut membawa dua rentang panjang yang tidak berurutan. Menyalin transisinya dan memisahkan sebuah clone akan memulihkan invarian tersebut.

Mengapa jumlah interval menghitung substring berbeda?

Interval state saling lepas (disjoint), dan setiap panjang yang direpresentasikan bersesuaian dengan satu substring berbeda. Oleh karena itu, menjumlahkan ukuran setiap interval akan menghitung setiap substring berbeda yang tidak kosong tepat satu kali.

Bagaimana SAM dan Aho–Corasick sebaiknya dibandingkan?

SAM mengindeks semua substring dari satu teks dan mendukung statistik agregat. Aho–Corasick mengindeks satu set pola yang diketahui untuk pencocokan batch. Apakah teks atau kumpulan pola yang bersifat tetap biasanya menentukan konstruksi mana yang lebih baik.

Bagaimana cara menemukan longest common substring?

Bangun SAM untuk S, lalu pindai T. Ikuti transisi sambil melacak panjang kecocokan saat ini; jika terjadi ketidakcocokan, ikuti suffix link dan coba lagi. Simpan panjang maksimum yang teramati.