การใช้งาน Longest palindrome in string ในภาษา Rust แบบง่ายๆ พร้อมตัวอย่าง

# การค้นหา Palindrome ที่ยาวที่สุดในข้อความด้วยภาษา Rust

สวัสดีครับ! ในโลกของการเขียนโปรแกรม เรามักพบกับปัญหาที่ท้าทายและมีความสวยงามทางคณิตศาสตร์ในเวลาเดียวกัน หนึ่งในปัญหาเหล่านั้นคือการค้นหาสตริง Palindrome ที่ยาวที่สุดภายในข้อความ สําหรับคนที่ยังไม่ทราบ Palindrome คือ สตริงที่สามารถอ่านจากหน้าไปหลังและจากหลังไปหน้าแล้วได้ผลเหมือนกัน เช่น "radar" หรือ "level" เป็นต้น ในบทความนี้ ผมจะอธิบายวิธีการใช้งาน `Longest palindrome in string` ในภาษา Rust โดยมีเป้าหมายเพื่อนำไปประยุกต์ใช้กับ usecase ในโลกจริง เพื่อความเข้าใจที่ดีขึ้น ผมจะรวมตัวอย่างโค้ดด้วย

อะละลากอริทึมของการค้นหา Palindrome

ก่อนที่เราจะเจาะลึกลงไปในโค้ด ควรเข้าใจก่อนว่าการค้นหาพาลินโดรมนั้นสามารถทำได้หลายวิธี วิธีที่ง่ายที่สุดคือการใช้ Brute Force ซึ่งมีการเช็คทุกๆ substring ในข้อความว่าเป็นพาลินโดรมหรือไม่ แน่นอนว่าวิธีนี้มีความซับซ้อนทางเวลาเป็น O(n^3) ทำให้ไม่เหมาะกับข้อความที่มีความยาวมากๆ เราจะแนะนำวิธีที่เหมาะสมและมีประสิทธิภาพกว่า

ตัวอย่างโค้ด 1: Brute Force Approach

 fn is_palindrome(s: &str) -> bool {
    s.chars().eq(s.chars().rev())
}

fn longest_palindrome(s: String) -> String {
    let mut longest = String::new();

    for i in 0..s.len() {
        for j in 0..=i {
            let substring = &s[j..=i];
            if is_palindrome(substring) && substring.len() > longest.len() {
                longest = substring.to_string();
            }
        }
    }
    longest
}

fn main() {
    let s = String::from("babad");
    println!("The longest palindrome is {}", longest_palindrome(s));
}

ในตัวอย่างนี้ เราใช้ฟังก์ชัน `is_palindrome` สำหรับการตรวจสอบว่า substring เป็นพาลินโดรมหรือไม่ และใช้ loop ทับซ้อนกันเพื่อหา substring ที่ยาวที่สุด

ตัวอย่างโค้ด 2: Dynamic Programming Approach

Dynamic Programming (DP) เป็นอีกหนึ่งทางเลือกที่มีประสิทธิภาพกว่า โดยมีเวลาในการทำงานเป็น O(n^2) และใช้หน่วยความจำเพิ่มเติม

 fn longest_palindrome(s: String) -> String {
    let len = s.len();
    let mut dp = vec![vec![false; len]; len];
    let mut start = 0;
    let mut max_length = 1;

    for i in 0..len {
        dp[i][i] = true;
        for j in 0..i {
            if s.chars().nth(j) == s.chars().nth(i) && (i - j < 3 || dp[j + 1][i - 1]) {
                dp[j][i] = true;
                if i - j + 1 > max_length {
                    start = j;
                    max_length = i - j + 1;
                }
            }
        }
    }
    s[start..start + max_length].to_string()
}

fn main() {
    let s = String::from("cbbd");
    println!("The longest palindrome is {}", longest_palindrome(s));
}

DP ทำงานโดยการเก็บสถานะของการเป็นพาลินโดรมของ substring ต่างๆ ลงในตารางที่เรียกว่า `dp` เพื่อนำค่าเหล่านั้นมาใช้ซ้ำในการคำนวณถัดๆ ไป

ตัวอย่างโค้ด 3: Expand Around Center Approach

วิธีเฉพาะเจาะจงอีกวิธีที่มีประสิทธิภาพต่อการค้นหาพาลินโดรมคือการขยายรอบจุดศูนย์กลาง ซึ่งเป็นวิธีที่มีประสิทธิภาพที่สุดในหมู่ทั้ง 3 วิธีที่กล่าวมา

 fn expand_around_center(s: &str, mut left: usize, mut right: usize) -> (usize, usize) {
    while left > 0 && right < s.len() - 1 && s.chars().nth(left - 1) == s.chars().nth(right + 1) {
        left -= 1;
        right += 1;
    }
    (left, right)
}

fn longest_palindrome(s: String) -> String {
    let mut start = 0;
    let mut end = 0;
    for i in 0..s.len() {
        let (left1, right1) = expand_around_center(&s, i, i);
        let (left2, right2) = expand_around_center(&s, i, i + 1);

        if right1 - left1 > end - start {
            start = left1;
            end = right1;
        }
        if right2 - left2 > end - start {
            start = left2;
            end = right2;
        }
    }
    s[start..=end].to_string()
}

fn main() {
    let s = String::from("forgeeksskeegfor");
    println!("The longest palindrome is {}", longest_palindrome(s));
}

โดยสรุป, `expand_around_center` จะใช้เทคนิคในการขยายสตริงฝั่งซ้ายและขวาออกไปเพื่อหาพาลินโดรมที่ยาวที่สุดที่มีจุดศูนย์กลางตรงกลางตัวแปร `i` นี้ถือว่าเป็นวิธีที่ประหยัดที่สุดเนื่องจากมีเวลาเฉลี่ยประมาณ O(n^2) แต่ในแง่ของการทำซ้ำจริง ๆ แล้วมันจะรวดเร็วกว่ามาก

Usecase ในโลกจริง

การหาพาลินโดรมในข้อความอาจไม่พบบ่อยใน applications ปกติ แต่ในแง่ของ bioinformatics หรือการวิเคราะห์ DNA sequences ที่อาจมี structures เป็น palindrome การหาพาลินโดรมที่ยาวที่สุดอาจช่วยในการประเมิน patterns ราวกับใช้ markers ซึ่งอาจเป็นส่วนสำคัญในการทำเครื่องหมายลำดับทางพันธุกรรมที่มีความสำคัญ

การเรียนรู้การทำโค้ดให้มีประสิทธิภาพสำหรับปัญหาย่อยเหล่านี้เป็นสิ่งสำคัญ ที่ EPT, นอกจากเนื้อหาทางทฤษฎีและเทคนิคปฏิบัติแล้ว เรายังส่งเสริมการคิดวิเคราะห์และการใช้โค้ดเพื่อจัดการกับปัญหาที่หลากหลาย หากคุณสนใจที่จะขยายความรู้ด้านการเขียนโปรแกรมของคุณ และต้องการเรียนรู้วิธีการใช้งานพาลินโดรมในการเขียนโปรแกรมแบบมืออาชีพ EPT ยินดีต้อนรับนักเรียนทุกระดับเพื่อร่วมสำรวจโลกแห่งการเขียนโค้ดกับเรา!

ุณสามารถศึกษาและฝึกฝนกับตัวอย่างโค้ดเหล่านี้ได้ และหากคุณพร้อมที่จะพัฒนาทักษะการเขียนโปรแกรมของคุณไปอีกขั้น ลองพิจารณาสมัครเรียนกับเราที่ EPT ซึ่งเรามีหลักสูตรที่เหมาะสมกับทั้งผู้ที่เริ่มต้นและผู้ที่ต้องการเสริมสร้างความรู้ด้านการเขียนโปรแกรมให้แข็งแกร่งขึ้น ด้วยครูผู้เชี่ยวชาญทั้งในทฤษฎีและปฏิบัติจะช่วยให้คุณก้าวทันเทคโนโลยีและเทคนิคการเขียนโปรแกรมล่าสุดในยุคสมัยนี้ ร่วมเดินทางในโลกแห่งการเขียนโปรแกรมกับเราวันนี้!

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