11. Tali

-

11. 1. Palindrom

Palindrom adalah kata atau frasa yang ejaannya sama persis ketika dibaca maju atau mundur. Palindrom boleh menggunakan huruf kecil atau huruf besar, mengandung spasi, tanda baca, dan pemisah kata.

Algoritma yang memeriksa palindrom adalah pertanyaan wawancara pemrograman yang umum.

Kata mobil balap adalah palindrom yang valid, karena merupakan kata yang dieja sama saat maju dan mundur. Contoh di bawah menunjukkan kasus palindrom racecar yang valid.

|     |
racecar -> r == r

 |   |
racecar -> a == a

  | |
racecar -> c == c

   |
racecar -> left index == right index -> return true

Untuk memeriksa palindrom, karakter suatu string dibandingkan mulai dari awal dan akhir kemudian bergerak ke dalam menuju tengah string dengan menjaga jarak yang sama. Dalam implementasi algoritma palindrom ini, rekursi digunakan untuk memeriksa setiap karakter di sisi kiri dan kanan yang bergerak ke dalam.

func isPalindrome(_ str: String) -> Bool {
    let strippedString = str.replacingOccurrences(of: "\\W", with: "", options: .regularExpression, range: nil)
    let length = strippedString.count
    
    if length > 1 {
        return palindrome(strippedString.lowercased(), left: 0, right: length - 1)
    }
    
    return false
}
private func palindrome(_ str: String, left: Int, right: Int) -> Bool {
    if left >= right {
        return true
    }
    
    let lhs = str[str.index(str.startIndex, offsetBy: left)]
    let rhs = str[str.index(str.startIndex, offsetBy: right)]
    
    if lhs != rhs {0
        return false
    }
    
    return palindrome(str, left: left + 1, right: right - 1)
}

11. 2. Algoritma Manajer

Algoritma Manacher merupakan algoritma untuk mencari palindrom dalam sebuah string, dan kompleksitas waktunya adalah O(n) (di mana n adalah panjang string)

Algoritme mengambil string S sebagai masukan dan mengembalikan:

  • Array bilangan bulat A mempunyai panjang yang sama dengan string S, dan elemen A [i] dari masing-masing A adalah panjang jari-jari radial terpanjang dari string ke-i (yaitu, S[(i−A[i]) ⋯(i+A[i])] adalah string yang terjual dan S[(i−A[i]−1)⋯(i+A[i]+1)] bukan string yang terjual )

Misalnya untuk input S = ‘pisang’, hasil A adalah:

Algoritmenya adalah sebagai berikut:

  1. saya melanjutkan dari 0 ke n-1 (n = | S |)
  2. R = max (j + A [j]) untuk semua j dengan j ‹ i, Misalkan j menjadi p. (R = hal + SEBUAH [p])
  3. nilai awal A [i] ditentukan tergantung ada tidaknya i ≤ R
  • Jika i› R, nilai awal A[i] adalah nol.
  • Jika i ≤ R, maka i adalah tempat pembuangan Soldin yang berpusat di p. Pada saat ini, kita memperoleh titik simetris i 'dari i di sekitar p. Nilai awal A[i] adalah min (R-i, A[i’])

4. Dari nilai awal A [i], A [i] dinaikan hingga S [i-A [i]] dan S [i + A [i]] sama, lalu ke i.

11. 3. Mencoba

Berarti kumpulan struktur data pohon terurut yang digunakan untuk menyimpan kumpulan dinamis atau larik asosiatif dengan string. Berbeda dengan pohon pencarian biner, node pada pohon tidak menyimpan kunci yang terkait dengan node tersebut. Sebaliknya, posisi pada pohon mewakili kunci saat ini. Setiap turunan dari node tertentu memiliki awalan yang sama dengan node tersebut, dan node root memiliki string kosong. Nilainya tidak ada di semua node, tetapi hanya ada di node daun atau node dalam yang sesuai dengan kunci tertentu. Untuk mengoptimalkan penggunaan ruang pohon awalan, pohon awalan kompak telah dibayangkan. Kata trie berasal dari kata reTRIEval. Edward Fredkin, yang menciptakan kata ini, mengucapkan kata tersebut sama dengan 'pohon', tetapi ada pula yang mengucapkannya sebagai 'trai'.

Mengapa saya harus menggunakan TRIE?
Untuk mencari informasi teks dalam jumlah besar dengan cepat dan efisien
Jadi Trie adalah struktur data yang dapat secara efektif mengambil kamus atau pelengkapan otomatis Internet.

Seperti disebutkan sebelumnya , nama TRIE berasal dari TREE RETRIEVAL. Ciri yang paling umum adalah informasi kata kunci hanya memiliki node terakhir, node sisanya tidak memiliki informasi dan hanya link.

11. 4. Pohon Akhiran

Pohon sufiks adalah struktur data berbentuk trie yang mewakili semua sufiks suatu string.
Trie disebut pohon prefiks. Perbedaan antara struktur datanya adalah ketika ada kata banana, trie hanya menyimpan kata banana, tetapi pohon sufiksnya seperti banana, anana, nana, ana, na, a Ini menyimpan jumlah semua kasus yang bisa datang dari kata pisang. Alasan menyimpan semua kasus dengan sia-sia adalah karena Anda perlu mencari string. Dalam kasus struktur data Trie, Anda dapat menemukan kata banana lengkap sebagai kata parsial seperti ban, ba, tetapi Anda tidak dapat menemukan banana dengan kata nan, ana. Untuk mengatasi masalah ini, tampaknya ada pohon sufiks yang meningkatkan trie.

Karena tepi dapat memiliki label string, perbedaan harus dibuat antara dua arti 'kedalaman'. Yang pertama adalah kedalaman node. Kedalaman node mengacu pada berapa banyak tepi yang harus dilalui dari akar ke node. Yang kedua adalah kedalaman Label. Ini adalah total panjang label tepi untuk tepi pada jalur dari akar ke simpul.