Title BigO_CP01_Lv3_Lecture09_Knuth-Morris-Pratt.pdf ✅

Competitive Programming LECTURE 09 Big-O Coding Website: www.bigocoding.com 1 KNUTH-MORRIS-PRATT
Competitive Programming Bài toán So khớp chuỗi (String Matching) là một bài toán phổ biến thường gặp trong các vấn đề xử lý chuỗi. Mô tả bài toán: cho một văn bản T và một mẫu P, hãy xác định những vị trí xuất hiện của P trong T. Có nhiều thuật toán khác nhau để giải quyết bài toán này: Brute Force, Knuth–Morris–Pratt (KMP), Z Function, Hash, Boyer-Moore, ... Ví dụ: • T = “ATATATGATAGATATGATAC” • P = “ATATGATAC” → P xuất hiện trong T tại vị trí 11 Giới thiệu 2
Competitive Programming Với mỗi trị trí i ở chuỗi T, ta kiểm tra xem nó có phải là vị trí xuất hiện của P hay không bằng cách so sánh lần lượt các ký tự j ở chuỗi P với ký tự i+j ở chuỗi T. Ý tưởng cơ bản: 3 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 A T A T A T G A T A G A T A T G A T A C 0 1 2 3 4 5 6 7 8 A T A T G A T A C T P