Xâu con | Câu 3 - Đề HSG tin 11 Nghệ An | Năm 2014 - 2015

Thứ hai - 19/06/2023 21:32 3.805 0

Đây là một bài khá hay, một bài toán thách thức về thuật toán. Xử lý thuật toán tốt thì mới ăn full test bài này, còn không thì chỉ ăn được 60% test. Trong bài này chúng ta sẽ sử dụng thuật toán Rabin-Karp để tìm xâu con có độ dài bằng K xuất hiện trong xâu ban đầu, đây là thuật toán sử dụng mã băm. Thuật toán Rabin-Karp là thuật toán tương đối khó giải thích, các bạn có thể tự tìm hiểu thêm. Ngoài việc sử dụng thuật toán Rabin-Karp thì ta còn phài dùng thêm thuật toán TÌM KIẾM NHỊ PHÂN thì mới chạy full test bài này.
Ngoài ra trong bài này các bạn sẽ thấy được yếu điểm của Python về tốc độ xử lý thuật toán. Cùng một thuật toán, nhưng Python xử lý chậm hơn Pascal rất nhiều lần! Đừng quên theo dõi Fanpage và đăng ký kênh YOTUBE của admin để xem như lời cảm ởn!

THUẬT TOÁN RABIN-KARP VÀ TÌM KIẾM NHỊ PHÂN

Bài 3. (6 điểm) Xâu con
Cho trước một xâu có độ dài L (1 < L < 2.10⁵) chỉ chứa các chữ cái thường trong bảng chữ cái tiếng Anh.
Yêu cầu: Hãy tìm xâu con dài nhất xuất hiện ít nhất 2 lần trong xâu đã cho.
Dữ liệu vào từ file XAU.INP:

Dòng đầu là một số nguyên L.
Dòng sau là một xâu có độ dài L.

Kết quả ghi ra file XAU.OUT: Chỉ một số duy nhất là độ dài của xâu con tìm được, nếu không tìm được thì ghi ra 0.
Ví dụ:

XAU.INP	XAU.OUT	XAU.INP	XAU.OUT	XAU.INP	XAU.OUT
11 sabcabcfabc	3	18 trutrutiktiktappop	4	6 abcdef	0

Lưu ý: Có 60% số test của bài có độ dài xâu L < 255
Có 40% số test của bài có độ dài xâu L >255

Ý tưởng ban đầu.

Sau khi đọc đề thì ý tưởng ban đầu sẽ là duyệt qua tất cả các xâu con (sub) của xâu L, sau đó dùng kỹ thuật đánh dấu để đếm xem sự xuất hiện của xâu con (sub) trong xâu L là bao nhiêu lần. Sau đó ta tìm các sub có giá trị > 1 và kiểm tra xâu nào có độ dài lớn nhất thì in độ dài xâu đó. Đối với Python, để sử dụng kỹ thuật đánh dấu ta thường dùng kiểu dữ liệu từ điển (dictionary) để đánh dấu số lần xuất hiện của xâu con (sub). Sau đây là code mẫu bằng Python: (Chú ý: phương thức get() trong kiểu biến dictionary là lấy giá trị của phần tử.)

# Đọc dữ liệu từ file
with open("xau.inp", "r") as f:
    L = int(f.readline().strip())  # Đọc độ dài xâu và chuyển sang kiểu int
    s = f.readline().strip()  # Đọc xâu và loại bỏ các ký tự xuống dòng

h = {}  # Khởi tạo một dictionary để lưu trữ giá trị Hash cho các xâu con
max_length = 0  # Khởi tạo giá trị độ dài của xâu con xuất hiện nhiều nhất là 0

# Duyệt qua tất cả các xâu con có thể có trong xâu s
for i in range(L):
    for j in range(i + 1, L + 1):
        sub = s[i:j]  # Lấy ra xâu con từ vị trí i đến j
        h[sub] = h.get(sub, 0) + 1  # Tăng giá trị của xâu con này trong từ điển lên 1(Đếm số lần xuất hiện)
# Tìm xâu con có độ dài lớn nhất xuất hiện ít nhất 2 lần
for sub, count in h.items():
    if count > 1 and len(sub) > max_length:
        max_length = len(sub)
        max_sub = sub

# Ghi kết quả ra file đầu ra XAU.OUT
with open('XAU.OUT', 'w') as f:
    f.write(max_length)

Trong code mình đã giải thích rõ nên mình không giải thích gì thêm nhé. Tuy nhiên, code trên nhìn có vẻ êm, nhưng đọc kỹ đề ta thấy chiều dài xâu L tới 2.10⁵mà trong code trên ta thấy để duyết hết xâu con của L thì cần 2 vòng lặp For lồng nhau, nên độ phức tạp là O(n²) chắc chắn không full test. Vậy để chạy full test bài này ta cần kết hợp thuật toán Rabin-Karp và tìm kiếm nhị phân.

Code mẫu bằng Pascal:

program XAU;

const
   MAXLEN  = 200000;
   MAXHASH = 200003;
   fi   = 'XAU.inp';
   fo   = 'XAU.out';
type node = record
   hash, key, next : longint;
end;

var
   nnodes         : longint;
   nodes          : array[1..MAXLEN] of node;
   tablica        : array[0..MAXHASH-1] of longint;
   L              : longint;
   str            : array[1..MAXLEN] of char;
   i, lo, hi, mid : longint;

col, ins:longint;

function trazi2(K : longint) : boolean;
var
   hash, sub, i, p, j : longint;
   isti               : boolean;
begin
   if K = 0 then begin
      trazi2 := true;
      exit;
   end;

   while nnodes > 0 do begin
      tablica[ nodes[nnodes].hash ] := -1;
      nnodes := nnodes-1;
   end;

   hash := 0; sub := 1;
   for i:=1 to K do begin
      sub := (26*sub) mod MAXHASH;
      hash := (26*hash + ord(str[i])) mod MAXHASH;
   end;

   sub := MAXHASH - sub;

   for i:=K to L do begin
      p := tablica[hash];
      while p <> -1 do begin
         isti := true;
         for j:=0 to K-1 do
            if str[ nodes[p].key+j ] <> str[ i-K+1+j ] then begin
               isti := false;
               break;
            end;

         if isti then begin
            trazi2 := true;
            exit;
         end;

         p := nodes[p].next;
      end;

      ins := ins+1;
      if tablica[hash] <> -1 then
         col := col+1;
      nnodes := nnodes+1;
      nodes[nnodes].hash := hash;
      nodes[nnodes].key  := i-K+1;
      nodes[nnodes].next := tablica[hash];
      tablica[hash] := nnodes;

      hash := (26*hash + sub*ord(str[i-K+1]) + ord(str[i+1])) mod MAXHASH;
   end;

   trazi2 := false;
end;

begin
   assign(input,fi);
   reset(input);
   assign(output,fo);
   rewrite(output);
   readln(L);
   for i:=1 to L do  read(str[i]);

   for i:=0 to MAXHASH-1 do    tablica[i] := -1;

   lo := 0; hi := L-1;
   while lo<hi do begin
      mid := (lo+hi+1) div 2;

      if trazi2(mid) then
         lo := mid
      else
         hi := mid-1;
   end;

   writeln(lo);
end.

Giải thích: (Code dài nên mình sẽ giải thích kỹ hơn từng biến)

Hàm `trazi2` sử dụng thuật toán Rabin-Karp để tìm kiếm chuỗi con có độ dài K xuất hiện trong chuỗi ban đầu được lưu trong mảng `str`.

Giải thích ý nghĩa của các biến toàn cục:

`nnodes`: số lượng node trong danh sách liên kết, mỗi node chứa thông tin về mã băm, vị trí bắt đầu của chuỗi con tương ứng và phần tử tiếp theo trong danh sách.
`nodes`: mảng lưu trữ các node của danh sách liên kết.
`tablica`: bảng băm, lưu trữ các vị trí xuất hiện của các chuỗi con trong chuỗi ban đầu. Mỗi phần tử của mảng chứa một số nguyên tương ứng với node đầu tiên của danh sách liên kết chứa chuỗi con tương ứng, hoặc -1 nếu không có chuỗi con nào.
`L`: độ dài của chuỗi ban đầu.
`str`: mảng lưu trữ các ký tự của chuỗi ban đầu.
`i`: vị trí hiện tại đang xét trong chuỗi ban đầu.
`lo`, `hi`, `mid`: biến để tìm kiếm độ dài chuỗi con cần tìm.
`col`, `ins`: biến đếm số lần so sánh và chèn node vào danh sách.

Hàm `trazi2` thực hiện các công việc sau:

Kiểm tra xem độ dài K có bằng 0 không, nếu có thì trả về True.
Xóa toàn bộ node trong danh sách liên kết và đặt giá trị tất cả phần tử trong bảng băm về -1.
Tạo mã băm cho chuỗi con đầu tiên có độ dài K.
Duyệt qua chuỗi ban đầu từ vị trí K đến L.
Tìm kiếm chuỗi con có độ dài K trong danh sách liên kết được lưu trữ trong bảng băm.
Nếu tìm thấy chuỗi con, trả về True.
Nếu không tìm thấy chuỗi con, tạo node mới cho chuỗi con này, thêm vào danh sách liên kết, và cập nhật bảng băm.
Tạo mã băm cho chuỗi con tiếp theo bằng cách loại bỏ ký tự ở đầu tiên và thêm một ký tự mới ở cuối cùng.
Sau khi duyệt xong, trả về False.

Để chạy hàm `trazi2` và tìm độ dài của chuỗi con, chương trình sử dụng phương pháp tìm kiếm nhị phân. Lần đầu tiên lựa chọn giá trị mid bằng trung bình của giá trị lo và hi. Nếu tìm thấy chuỗi con có độ dài mid, lo sẽ được gán với mid. Nếu không tìm thấy chuỗi con, giá trị hi sẽ được gán bằng mid-1. Thực hiện đến khi lo bằng giá trị hi. Cuối cùng, độ dài của chuỗi con tìm được được ghi vào file đầu ra.

Chuyển code Pascal sang Python để so sánh tốc độ.

Sau đây mình sẽ chuyển code Pascal trên thành code Python để so sánh tốc độ chạy, Để các bạn dễ so sánh về code Pascal và Python mình sẽ viết lại một cách tương đồng nhất có thể, mời các bạn tham khảo code Python:

MAXLEN = 200000
MAXHASH = 200003
fi = 'XAU.inp'
fo = 'XAU.out'

class Node:
    def __init__(self, hash_val=0, key=0, next_node=-1):
        self.hash = hash_val
        self.key = key
        self.next = next_node

def trazi2(K):
    global tablica, nnodes, nodes, my_str, L, col, ins

    if K == 0:
        return True

    while nnodes > 0:
        tablica[nodes[nnodes].hash] = -1
        nnodes -= 1

    hash_val, sub = 0, 1
    for i in range(K):
        sub = (26 * sub) % MAXHASH
        hash_val = (26 * hash_val + ord(my_str[i])) % MAXHASH

    sub = MAXHASH - sub

    ins = 0
    for i in range(K-1, L):
        p = tablica[hash_val]

        while p != -1:
            isti = True

            for j in range(K):
                if my_str[nodes[p].key + j] != my_str[i - K + 1 + j]:
                    isti = False
                    break

            if isti:
                return True

            p = nodes[p].next

        ins += 1

        if tablica[hash_val] != -1:
            col += 1

        nnodes += 1
        nodes[nnodes] = Node(hash_val, i - K + 1, tablica[hash_val])
        tablica[hash_val] = nnodes

        if i < L - 1:
            hash_val = (26 * hash_val + sub * ord(my_str[i - K + 1]) + ord(my_str[i + 1])) % MAXHASH

    return False

with open(fi, 'r') as f_in, open(fo, 'w') as f_out:
    L = int(f_in.readline())
    my_str = f_in.readline().strip()

    tablica = [-1] * MAXHASH
    nodes = [Node() for _ in range(MAXLEN)]
    nnodes = 0

    lo, hi = 0, L - 1

    while lo < hi:
        mid = (lo + hi + 1) // 2

        if trazi2(mid):
            lo = mid
        else:
            hi = mid - 1
    f_out.write(str(lo))

Các bạn phải chạy cả hai chương trình bằng Pascal và Python sẽ thấy Python chậm hơn Pascal rất nhiều lần.