11. เชือก

11. 1. พาลินโดรม

พาลินโดรมคือคำหรือวลีที่สะกดเหมือนกันทุกประการเมื่ออ่านไปข้างหน้าหรือข้างหลัง พาลินโดรมได้รับอนุญาตให้เป็นตัวพิมพ์เล็กหรือตัวพิมพ์ใหญ่ โดยมีการเว้นวรรค เครื่องหมายวรรคตอน และตัวแบ่งคำ

อัลกอริทึมที่ตรวจสอบพาลินโดรมเป็นคำถามสัมภาษณ์การเขียนโปรแกรมทั่วไป

คำว่า racecar เป็นพาลินโดรมที่ถูกต้อง เนื่องจากเป็นคำที่สะกดเหมือนกันทั้งตอนพื้นหลังและข้างหน้า ตัวอย่างด้านล่างแสดงกรณีที่ถูกต้องของพาลินโดรม racecar

|     |
racecar -> r == r

 |   |
racecar -> a == a

  | |
racecar -> c == c

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

ในการตรวจสอบหาพาลินโดรม อักขระของสตริงจะถูกเปรียบเทียบโดยเริ่มจากจุดเริ่มต้นและจุดสิ้นสุด จากนั้นจึงเลื่อนเข้ามาตรงกลางของสตริงโดยยังคงรักษาระยะห่างเท่าเดิม ในการใช้งานอัลกอริธึมพาลินโดรมนี้ การเรียกซ้ำจะใช้เพื่อตรวจสอบอักขระแต่ละตัวทางด้านซ้ายมือและด้านขวามือที่เคลื่อนเข้าด้านใน

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. อัลกอริทึมของ Manacher

อัลกอริทึมของ Manacher เป็นอัลกอริทึมสำหรับการค้นหาพาลินโดรมในสตริง และความซับซ้อนของเวลาคือ O (n) (โดยที่ n คือความยาวของสตริง)

อัลกอริทึมใช้สตริง S เป็นอินพุตและส่งกลับ:

อาร์เรย์จำนวนเต็ม A ที่มีความยาวเท่ากับสตริง S และองค์ประกอบ A [i] ของแต่ละ A คือความยาวของรัศมีรัศมีที่ยาวที่สุดของสตริงที่ i (กล่าวคือ S[(i−A[i]) ⋯(i+A[i])] คือสตริงที่ขายแล้ว และ S[(i−A[i]−1)⋯(i+A[i]+1)] ไม่ใช่สตริงที่ขาย )

ตัวอย่างเช่น สำหรับอินพุต S = 'banana' ผลลัพธ์ของ A คือ:

อัลกอริทึมเป็นดังนี้:

ฉันดำเนินการจาก 0 ถึง n-1 (n = | S |)
R = สูงสุด (j + A [j]) สำหรับ j ทั้งหมดที่มี j ‹ i ให้ j เป็น p (R = พี + A [พี])
ค่าเริ่มต้นของ A [i] ถูกกำหนดขึ้นอยู่กับว่า i ≤ R หรือไม่

ถ้า i› R ค่าเริ่มต้นของ A [i] จะเป็นศูนย์
ถ้า i ≤ R แล้ว i จะเป็นดัมพ์การขายที่มีศูนย์กลางอยู่ที่ p ในเวลานี้ เราได้จุดสมมาตร i 'ของฉันรอบ p ค่าเริ่มต้นของ A [i] คือ min (R-i, A [i ‘])

4. จากค่าเริ่มต้นของ A [i] A [i] จะเพิ่มขึ้นจนกระทั่ง S [i-A [i]] และ S [i + A [i]] เท่ากัน จากนั้นถึง i

11. 3. ทรี

หมายถึงชุดลำดับของโครงสร้างข้อมูลต้นไม้ที่ใช้ในการจัดเก็บชุดไดนามิกหรืออาร์เรย์ที่เชื่อมโยงด้วยสตริง ไม่เหมือนกับแผนผังการค้นหาแบบไบนารี โหนดบนแผนผังจะไม่เก็บคีย์ที่เกี่ยวข้องกับโหนดนั้น ตำแหน่งบนแผนผังแสดงถึงคีย์ปัจจุบันแทน ผู้สืบทอดทุกโหนดของโหนดใดโหนดหนึ่งจะมีคำนำหน้าเหมือนกันกับโหนด และโหนดรูทจะมีสตริงว่าง ค่าไม่มีอยู่ในโหนดทั้งหมด แต่มีเฉพาะที่โหนดปลายสุดหรือโหนดด้านในที่สอดคล้องกับคีย์เฉพาะเท่านั้น เพื่อเพิ่มประสิทธิภาพการใช้พื้นที่ของทรีคำนำหน้า จึงมีจินตนาการถึงทรีคำนำหน้าขนาดกะทัดรัด คำว่า trie มาจากคำว่า reTRIEval Edward Fredkin ผู้สร้างคำนี้ ออกเสียงคำเดียวกับ 'tree' แต่คนอื่นๆ ออกเสียงว่า 'trai'

เหตุใดฉันจึงควรใช้ TRIE
เพื่อการค้นหาข้อมูลข้อความจำนวนมากอย่างรวดเร็วและมีประสิทธิภาพ
ดังนั้น Trie จึงเป็นโครงสร้างข้อมูลที่สามารถดึงพจนานุกรมหรือการเติมข้อความอัตโนมัติทางอินเทอร์เน็ตได้อย่างมีประสิทธิภาพ

ตามที่กล่าวไว้ก่อนหน้านี้ ชื่อ TRIE มาจาก TREE RETRIEVAL ลักษณะทั่วไปมากที่สุดคือข้อมูลคำหลักมีเพียงโหนดสุดท้าย โหนดที่เหลือไม่มีข้อมูลและมีเพียงลิงก์เท่านั้น

11. 4. ต้นไม้ต่อท้าย

Suffix tree เป็นโครงสร้างข้อมูลรูป trie ที่แสดงถึงส่วนต่อท้ายทั้งหมดของสตริง
trie เรียกว่า prefix tree ความแตกต่างระหว่างโครงสร้างข้อมูลคือเมื่อมีคำว่า Banana คำว่า Trie จะเก็บเฉพาะคำว่า Banana แต่ต้นไม้ต่อท้ายจะเป็นเช่น Banana, Anana, nana, ana, na, a จะบันทึกจำนวนกรณีทั้งหมดที่ได้มา มาจากคำว่ากล้วย เหตุผลในการจัดเก็บเคสทั้งหมดอย่างไร้ประโยชน์ก็เพราะคุณต้องค้นหาสตริง ในกรณีของโครงสร้างข้อมูล Trie คุณสามารถค้นหาคำว่า Banana แบบเต็มได้เป็นคำบางส่วน เช่น ban, ba แต่คุณไม่สามารถหาคำว่า nan, ana ได้ เพื่อแก้ปัญหานี้ ดูเหมือนว่าจะเป็นต้นไม้ต่อท้ายที่ช่วยปรับปรุงไตร

เนื่องจากขอบสามารถมีป้ายชื่อสตริงได้ จึงต้องสร้างความแตกต่างระหว่างสองความหมายของ 'ความลึก' ประการแรกคือความลึกของโหนด ความลึกของโหนดหมายถึงจำนวนขอบที่ต้องผ่านจากรูทไปยังโหนด ประการที่สองคือความลึกของฉลาก นี่คือความยาวรวมของป้ายกำกับขอบสำหรับขอบในเส้นทางจากรูทถึงโหนด

11. เชือก