tailieunhanh - Cẩm nang thuật toán tập 1 part 9

Tham khảo tài liệu 'cẩm nang thuật toán tập 1 part 9', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | 336 TỈM KIẾM CHUỖI và tìm được sự trùng khóp hoàn toàn. Phương pháp này đưa chúng ta tới đúng vị trí khỏp nhau với cái giá là chỉ cân kiểm tra qua 7 ký tự trong văn bản và thèm 5 ký tự nữa để kiểm tra sự trùng khớp . Thuật toán ký-tự-không-khóp mismatched-character này thật dễ cài đặt. Đơn giản là nâng cấp phép quét mảu brute-force từ phải-sang-trái để khởi động một mãng skip mà nó cho biết là ứng với mối ký tự trong bàng chữ cái ta phải nhảy qua một khoảng bao nhiêu nếu ký tự đó xuất hiện trong văn bân và gây ra sự không ăn khớp trong khi tim chuỗi. Phải có một điểm vào entry trong màng skip cho mỗi ký tự có thể xây ra trong văn bân để đơn giản giả sử Tầng ta đã có một hàm function index c char ũnteger mà nó trả vê 0 đối với các khoảng trắng và i đối với ký tự thứ i của bảng chữ cái ta cũng già sử rằng có một thù tục procedure initskỉp mà nó khởi dông giá trị màng skip là M đối với các ký tự không có trong mẫu và sau đó với j chạy từ 1 tởi M đặt skip index p j là M-j. Cài đặt thì đơn giản function mischarsearch integer var ij integer begin i M j M initskip repeat ư tiiiỉ pỊjì then begin i i- 1 j j-l end else begin if M-j l skiplindex aỉiị ỉ then i i M-j l else i i skiplindex aỊiỊ ỉ j M end until j 1 or a N mischarseareh i 1 end Lênh i i M-j 1 đặt lại i trò tới vị trí kế tiếp trong chuồi văn bản vì mẫu dịch chuyển từ trái sang phải ngang qua nó còn lệnh j M đặt lại con trô mẫu để chuẩn bị cho mồt phép so khớp từng ký tự từ phải sang trái. Lệnh kế đó dịch chuyển mâu qua văn bản nếu được trao đĩêu khiển. Đối với mẫu STING điểm vào trong THUẬT TOÁN BOYER-MOORE _ _Ể_ 337 mãng skip cho G sẽ ỉà 0 điểm vào cho N sẽ là 1 điểm vào cho I sẽ là 2 điểm vào cho T sẽ là 3 điểm vào cho s sè là 4 và các điểm vào cho tất cả các ký tự khác sẽ là 5. Vì vậy ví dụ khi bắt gặp một ký tự s trong một lân tìm từ phải sang trái con trỏ i sẽ được tăng thêm 4 sao cho cuối của mảu được sắp thành hàng bốn vị trí VẾ bên phải của s và kết quả là s trong mẫu ứng với s trong vàn .