Suffix array va matnni suffix array’da qayta ishlash

Bizga N belgiga ega matndan so’zni qidirib, barcha so’zlarni topish kerak bo’lsin.

To’g’ri, so’zni topadigan tayyor sub-string funksiyalar allaqachon mavjud. Ammo texnik intervyu jarayonida qo’yiladigan masalada tayyor funksiyadan foydalanmaslik kerak bo’ladi. Bunda odatiy yechim – brute-force algoritmi yordamida matndagi barcha belgilar solishtirib chiqiladi. Ishlash vaqti – O(N2), tezkor yechim emas.

Biz masalani linear vaqtda – O(N) da yecha olamizmi?

Ha, suffix array va suffix sort yo’li bilan barcha so’zlarni linear vaqt ichida topishning imkoni bor ekan.

Bizda quyidagi string – “itwasbestitwasw” dan barcha “itwas” iborasini topish kerak bo’lsin. Javascriptdan bilamizki, stringdagi har bir belgi o’zining indeksiga ega. Masalan str[1] t ni qaytaradi.

itwasbestitwasw
01234567891011121314

Stringdan kerakli qismini olish – substring() yordamida amalga oshiriladi. Uning ishlash vaqti – O(N) ga teng.

Biz stringdan suffix array yasab olamiz. Suffix array – bu N belgili stringning [i…N-1] belgilaridan iborat array. Bunda i – iterator soni.

[
  'itwasbestitwasw',
  'twasbestitwasw',
  'wasbestitwasw',
  'asbestitwasw',
  'sbestitwasw',
  'bestitwasw',
  'estitwasw',
  'stitwasw',
  'titwasw',
  'itwasw',
  'twasw',
  'wasw',
  'asw',
  'sw',
  'w'
]

Array’ni tartiblab olamiz. Tartiblashda time complexity’ni O(N) ga erishish uchun, masalan 3-way radix quicksort‘dan foydalangan ma’qul:

[
  'asbestitwasw',
  'asw',
  'bestitwasw',
  'estitwasw',
  'itwasbestitwasw',
  'itwasw',
  'sbestitwasw',
  'stitwasw',
  'sw',
  'titwasw',
  'twasbestitwasw',
  'twasw',
  'w',
  'wasbestitwasw',
  'wasw'
]

Keyin suffix array’da binary search orqali qidirilayotgan so’zni topamiz.

[
  'asbestitwasw',
  'asw',
  'bestitwasw',
  'estitwasw',
  'itwasbestitwasw',
  'itwasw',
  'sbestitwasw',
  'stitwasw',
  'sw',
  'titwasw',
  'twasbestitwasw',
  'twasw',
  'w',
  'wasbestitwasw',
  'wasw'
]

Longest repeated substring

Yana bir keng tarqalgan muhim masalalardan biri – matndan eng uzun takrorlanuvchi iborani (longest repeated substring) topish kerak bo’lsin. Matn esa juda-juda katta – million, milliard belgilardan iborat. Amaliyotda bu kabi masalalarga genom ma’lumotlarini o’rganishda yoki kriptotahlilda duch kelinadi. Yana bir uchraydigan ko’rinishi – ma’lumotni siqish jarayonida (arxivlashda) qaytariluvchi iboralarni qisqartirish uchun ham kerak bo’ladi.

Katta matnlarda eng uzun takrorlanuvchi iborani topish uchun brute-force algoritmi samarasiz hisoblanadi, chunki uning ishlash vaqti – O(D * N2) ga teng, bunda D – eng uzun takrorlanuvchi iboradagi belgilar soni.

Biz bu masala uchun ham suffix sort yechimini qo’llay olamiz.

Bizda quyidagi matn bor:

aacaagttcacaagc
01234567891011121314

Undan suffix array yasab olamiz:

[
   'aacaagtttacaagc',
   'acaagtttacaagc',
   'caagtttacaagc',
   'aagtttacaagc',
   'agtttacaagc',
   'gtttacaagc',
   'tttacaagc',
   'ttacaagc',
   'tacaagc',
   'acaagc',
   'caagc',
   'aagc',
   'agc',
   'gc',
   'c'
 ]

Array’ni tartiblaymiz:

[
   'aacaagtttacaagc',
   'aagc',
   'aagtttacaagc',
   'acaagtttacaagc',
   'acaagc',
   'agc',
   'agtttacaagc',
   'c'
   'caagc',
   'caagtttacaagc',
   'gc',
   'gtttacaagc',
   'tacaagc',
   'ttacaagc',
   'tttacaagc',
 ]

Qaytariladigan iboralar yonma-yon joylashadi. Yana bir marta array’ni tekshirib chiqib, qaytariladigan iboralar ichidan eng uzunini topamiz.

[
   'aacaagtttacaagc',
   'aagc',
   'aagtttacaagc',
   'acaagtttacaagc',
   'acaagc',
   'agc',
   'agtttacaagc',
   'c'
   'caagc',
   'caagtttacaagc',
   'gc',
   'gtttacaagc',
   'tacaagc',
   'ttacaagc',
   'tttacaagc',
 ]

Longest repeated substring uchun kod