Chuỗi (string) là một loại dữ liệu cơ bản thường được sử dụng trong rất nhiều các hệ thống và là thành phần cơ bản trong các hệ thống xử lý văn bản (wordprocessing-system), các hệ thống này cung cấp cho ta rất nhiều khả năng để xử lý văn bản. Ngoài ra một vài các hệ thống đồ hoạ trên máy tính (computer graphics system) biểu diễn các hình ảnh như là các chuỗi nhị phân. Các thao tác trên chuỗi chúng ta thường gặp một số các phép toán cơ bản như: - Phép tìm kiếm một chuỗi. | CHUỖI VÀ CÁC BÀI TOÁN TRÊN CHUỖI Chuỗi string là một loại dữ liệu cơ bản thường được sử dụng trong rất nhiều các hệ thống và là thành phần cơ bản trong các hệ thống xử lý văn bản wordprocessing-system các hệ thống này cung cấp cho ta rất nhiều khả năng để xử lý văn bản. Ngoài ra một vài các hệ thống đồ hoạ trên máy tính computer graphics system biểu diễn các hình ảnh như là các chuỗi nhị phân. Các thao tác trên chuỗi chúng ta thường gặp một số các phép toán cơ bản như - Phép tìm kiếm một chuỗi con trong một chuỗi. - Phép thay thế một chuỗi con của một chuỗi bởi một chuỗi khác. - Phép chen chuỗi con vào một chuỗi. - Phép loại bỏ một chuỗi con của một chuỗi. Trong các phép toán nêu trên thì phép tìm kiếm trên chuỗi là phép toán quan trọng và thường gặp vì vậy ta chỉ tìm hiểu các giải thuật liên quan đến phép toán này đó là 1. Giải thuật Brute-Force. 2. Giải thuật Knuth-Morris-Pratt. 3. Giải thuật Boyer-Moore. 1. Các khái niện cơ bản về chuỗi . Chuỗi và phân chia chuỗi a. Định nghĩa chuôi Chuỗi là một dãy các ký tự được chứa trong một vùng liên tục của bộ nhớ. Các ký tự này có thể là ký tự chữ ký tự số hoặc ký tự đặc biệt. Chuỗi ký tự text string có thể được xem như là dãy các chữ các số và các ký tự đặc biệt. Một loại chuỗi khác là chuỗi nhị phân binary string đó là một dãy các kí tự 0 và 1. Vâ Minh Pha - Ba m n Khoa hãc my tĩnh 1 b. Độ dài chuỗi. Số ký tự của chuỗi được gọi là chiều dài của chuỗi. Mỗi ký tự chiếm 1 byte. Một chuỗi có thể có chiều dài bằng 0 gọi là chuỗi rỗng null string ký hiệu là Một chuỗi có thể được chia làm nhiều phần mỗi phần là một chuỗi con sub string . Các chuỗi con có thể có chiều dài bằng nhau hoặc khác nhau. . Cách phân chia chuỗi a. Dùng ký tự đặc biệt. Dùng ký tự trống blank để phân chia chuỗi con. Khi đó các chuỗi con có thể khác nhau. Để truy xuất một chuỗi con trong chuỗi thì ta phải tìm kiếm từ đầu chuỗi. Do đó tốc độ truy xuất của phương pháp này chậm. b. Dùng chiều dài cố định. Ta chia các chuỗi con thành các phần bằng nhau.
