บทนำ Knuth-Morris-Pratt (KMP) เป็นอัลกอริทึมค้นหาแพทเทิร์นที่ตรวจสอบตัวอักษรจากซ้ายไปขวา เมื่อแพทเทิร์นมี Sub-pattern ซ้ำกัน จะใช้คุณสมบัตินี้เพื่อเพิ่มประสิทธิภาพ ทั้งกรณีทั่วไปและกรณีแย่ที่สุด ความซับซ้อนของเวลา (Time Complexity) O(n) โดย n คือความยาวข้อความหลัก อินพุตและเอาต์พุต Input: Main St

บทนำ อัลกอริทึม Manacher ใช้หา Substring แบบ Palindrome (อ่านจากหน้าหลังได้เหมือนกัน) ที่ยาวที่สุดในสตริง โดยเลือกตัวอักษรแต่ละตัวเป็นศูนย์กลาง แล้วขยายไปซ้าย-ขวา มีอาร์เรย์เก็บข้อมูลความยาว Palindrome ที่ศูนย์กลางแต่ละตำแหน่ง ความซับซ้อนของเวลา (Time Complexity) O(n) โดย n คือความยาวสตริง อินพุต

บทนำ Naive Pattern Searching เป็นวิธีง่ายที่สุดในการค้นหาแพทเทิร์น ตรวจสอบตัวอักษรทุกตัวของข้อความหลักกับแพทเทิร์น เหมาะสำหรับข้อความขนาดเล็ก ไม่ต้องมีขั้นตอน Pre-processing และไม่ใช้พื้นที่เพิ่มเติม ความซับซ้อนของเวลา (Time Complexity) O(m × n) โดย m คือขนาดแพทเทิร์น และ n คือขนาดข้อความหลัก อิน

บทนำ Rabin-Karp เป็นอัลกอริทึมค้นหาแพทเทิร์นที่มีประสิทธิภาพ ใช้วิธีเลื่อนหน้าต่าง (Sliding Window) แต่แทนที่จะตรวจสอบตัวอักษรทุกตัวทุกครั้ง จะคำนวณค่า Hash ก่อน เมื่อค่า Hash ตรงกันจึงตรวจสอบตัวอักษรจริง ทำให้เร็วขึ้นในกรณีทั่วไป ความซับซ้อนของเวลา (Time Complexity) O(m + n) ในกรณีทั่วไป แต่กรณีแ

บทนำ จากสตริงที่กำหนด สามารถหา Suffix ทั้งหมดได้ หลังจากเรียงลำดับ Suffix ตามลำดับเล็กซิโคกราฟิก (Lexicographical Order) จะได้ Suffix Array สามารถสร้างได้จาก Suffix Tree ด้วยการท่อง DFS Suffix Array ช่วยค้นหา Suffix ได้ในเวลาเชิงเส้น และค้นหา Substring ได้ด้วยกระบวนการแบบ Binary Search ความซับซ้อ

บทนำ จากข้อความสามารถสร้าง Suffix ทั้งหมดเป็นโครงสร้างต้นไม้ (Tree) ทุกแพทเทิร์นที่ปรากฏในข้อความ ต้องเป็น Prefix ของ Suffix อย่างน้อยหนึ่งในข้อความ โดยการสร้าง Trie ของ Suffix ทั้งหมด สามารถค้นหา Substring ใดๆ ได้ในเวลาเชิงเส้น ทุก Suffix จบด้วยสัญลักษณ์สิ้นสุดสตริง จากแต่ละโหนด หากมีเส้นทางต่อไป

บทนำ อัลกอริทึม Z เรียกเช่นนี้เพราะต้องสร้างอาร์เรย์ Z ซึ่งมีขนาดเท่ากับความยาวของข้อความ (Text) อาร์เรย์นี้เก็บความยาวของสตริงย่อย (Substring) ที่ยาวที่สุดที่เริ่มจากตัวอักษรปัจจุบันของข้อความหลัก ขั้นแรก รวมแพทเทิร์น (Pattern) และข้อความหลัก (Text) ด้วยสัญลักษณ์พิเศษที่ไม่ปรากฏในทั้งสอง เช่น P$T

บทนำ ในกราฟไม่มีทิศทาง (Undirected Graph) เส้นทางแฮมิลตัน (Hamiltonian Path) คือเส้นทางที่ผ่านทุกโหนด (Vertex) ครบเพียงครั้งเดียว ส่วนวงจรแฮมิลตัน (Hamiltonian Cycle) คือเส้นทางแฮมิลตันที่มีเส้นขอบเชื่อมจากโหนดสุดท้ายกลับไปยังโหนดแรก ปัญหานี้คือการตรวจสอบว่ากราฟมีวงจรแฮมิลตันหรือไม่ และพิมพ์วงจรออ

บทนำ อัลกอริทึม Kruskal เป็นอีกวิธีหนึ่งในการหาต้นไม้ครอบคลุมน้ำหนักขั้นต่ำ (MST) จากกราฟที่เชื่อมต่อ G(V, E) โดยมีน้ำหนักเส้นขอบกำหนดไว้ หลักการทำงาน ใช้แนวคิด Merge-Tree Approach เริ่มต้นด้วยต้นไม้แยกกันหลายต้น (แต่ละโหนดเป็นต้นไม้ตัวเดียว) จากนั้นรวมต้นไม้โดยเลือกเส้นขอบที่มีน้ำหนักน้อยที่สุดที

บทนำ กำหนดชุดเหรียญ C(c1, c2, ..., Cn) และค่าเงิน V ต้องการหาจำนวนเหรียญน้อยที่สุดที่รวมกันได้ค่า V โดยสมมติว่าเหรียญแต่ละประเภทมีจำนวนไม่จำกัด ในตัวอย่างนี้ใช้ชุดเหรียญ {1, 2, 5, 10} เช่น สำหรับค่า 22 จะเลือก {10, 10, 2} ใช้ 3 เหรียญ ความซับซ้อนของเวลา (Time Complexity) O(V) โดยที่ V คือค่าเงินท

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

บทนำ อัลกอริทึม Prim เป็นหนึ่งในอัลกอริทึมที่ใช้หาต้นไม้ครอบคลุมน้ำหนักขั้นต่ำ (Minimum Spanning Tree - MST) จากกราฟที่เชื่อมต่อกัน (Connected Graph) G(V, E) โดยที่แต่ละเส้นขอบ (Edge) มีน้ำหนักหรือค่าใช้จ่ายกำหนดไว้ หลักการทำงาน อัลกอริทึมนี้ใช้แนวคิด Growing Tree Approach เริ่มจากจุดเริ่มต้น (See

Prims Algorithm หา Minimum Spanning Tree (MST) ของกราฟเชื่อมต่อแบบ Undirected Weighted Graph ใช้ Adjacency List และ Priority Queue ทำให้ได้ Time Complexity O(E log V) ความซับซ้อน (Complexity) Representation Time Complexity Adjacency Matrix O(V²)

Fractional Knapsack Problem เป็นปัญหาเพิ่มค่าสูงสุด (Maximize Value) โดยมีข้อจำกัดน้ำหนัก (Weight Capacity) W แตกต่างจาก 0-1 Knapsack ที่ สามารถแบ่งสิ่งของเป็นเศษส่วนได้ ความแตกต่าง 0-1 vs Fractional ด้าน 0-1 Knapsack Fractional Knapsack แบ่งสิ่งของไ

Aho-Corasick Algorithm เป็นอัลกอริทึม Multi-pattern String Matching ค้นหา หลาย Pattern พร้อมกัน ใน Text เดียวได้ในเวลา Linear ใช้โครงสร้าง Trie (Prefix Tree) พร้อม Failure Links และ Output Links 3 ขั้นตอนหลัก Go-to (Trie Construction): สร้าง Trie จาก Patterns ทั้งหมด Failure (Failure Links): ส

Anagram Pattern Search ค้นหาทุกตำแหน่งใน Text ที่มี Anagram (การจัดเรียงตัวอักษรใหม่) ของ Pattern ปรากฏขึ้น ไม่ใช่ค้นหา Pattern ตรงๆ แนวคิดการทำงาน สร้าง Frequency Array ของ Pattern (ขนาด 26 สำหรับ A-Z) Sliding Window ขนาด = Pattern Length วิ่งผ่าน Text สร้าง Frequency Array ของแต่ละ Window

Bad Character Heuristic เป็นหนึ่งใน 2 Heuristics ของ Boyer-Moore Algorithm (อีกคือ Good Suffix) ใช้ตารางเก็บ ตำแหน่งสุดท้าย (Rightmost occurrence) ของแต่ละตัวอักษรใน Pattern แนวคิดการทำงาน สร้างตาราง badChar[256] เก็บ index สุดท้ายของแต่ละ ASCII character ใน Pattern (ไม่พบ = -1) จับคู่ Pattern

Boyer-Moore Algorithm เป็นอัลกอริทึมค้นหา Pattern ใน String ที่เร็วที่สุดในทางปฏิบัติ ใช้ 2 Heuristics: Bad Character Rule และ Good Suffix Rule บทความนี้ครอบคลุม Good Suffix Heuristic แนวคิด Good Suffix Heuristic เมื่อพบการ Match บางส่วน (Suffix ของ Pattern ตรงกับ Substring ของ Text) ให้เลื่อน Patt

Quick Sort เป็นอัลกอริทึมจัดเรียงแบบ Divide and Conquer ที่ได้รับความนิยมมากที่สุดในทางปฏิบัติ เนื่องจากเร็วที่สุดในเฉลี่ย (Cache-friendly, In-place) ความซับซ้อน (Complexity) กรณี Time Complexity Best Case O(n log n) Average Case

Radix Sort เป็นอัลกอริทึมจัดเรียงแบบ Non-comparison (ไม่เปรียบเทียบ) จัดเรียงจำนวนเต็มโดยประมวลผลทีละ หลัก (Digit) เริ่มจากหลักหน่วย (LSD) หรือหลักสูงสุด (MSD) ใช้ Counting Sort เป็น Subroutine ความซับซ้อน (Complexity) ประเภท ความซับซ้อน Time Complexity