Title BigO_Lv4_Lecture01_Knuth-Morris-Pratt.pdf ✅

Competitive Programming LECTURE 01 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 Ý tưởng cơ bản (2): 4 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 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