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.
| i | t | w | a | s | b | e | s | t | i | t | w | a | s | w |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
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:
| a | a | c | a | a | g | t | t | c | a | c | a | a | g | c |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
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', ]