Test Set 1

Trong Test Set 1, mỗi mẫu buộc đáp án của ta phải có một hậu tố nhất định, và trước tiên ta cần kiểm tra xem các mẫu có đưa ra những yêu cầu mâu thuẫn nhau đối với hậu tố đó hay không.

Xét các chuỗi chữ cái đứng sau dấu sao ở đầu mỗi mẫu. Ta tìm chuỗi dài nhất trong số đó (nếu có nhiều chuỗi cùng dài nhất thì chọn chuỗi nào cũng được) và gọi chuỗi ấy là \(L\). Khi đó tồn tại ít nhất một đáp án khi và chỉ khi mọi chuỗi còn lại đều là hậu tố của \(L\); ở đây chính \(L\) cũng được xem là một hậu tố của \(L\). Ta có thể kiểm tra từng chuỗi còn lại với \(L\) bằng cách bắt đầu từ cuối hai chuỗi rồi đồng thời lùi về phía trước, cho tới khi gặp hai chữ cái khác nhau hoặc đã xét hết các chữ cái cần kiểm tra. Nếu từng gặp một vị trí khác nhau thì bộ test không có đáp án; ngược lại, ta biết rằng chính \(L\) là một đáp án hợp lệ.

Điều kiện này vừa cần vừa đủ: mọi đáp án đều phải kết thúc bằng phần sau dấu sao của từng mẫu; nếu không có mâu thuẫn thì hậu tố dài nhất \(L\) đã chứa mọi hậu tố ngắn hơn ở cuối nó.

Test Set 2

Trong Test Set 2, ta có thể chia các mẫu thành ba loại: (1) mẫu bắt đầu bằng một dấu sao, (2) mẫu kết thúc bằng một dấu sao, và (3) mẫu có dấu sao ở giữa.

Mẫu loại (1) yêu cầu từ được xuất ra có một hậu tố nhất định, giống như trong Test Set 1. Mẫu loại (2) yêu cầu từ được xuất ra có một tiền tố nhất định. Mẫu loại (3) đưa ra cả hai yêu cầu này; ta có thể tách nó thành một yêu cầu về hậu tố và một yêu cầu về tiền tố, rồi xử lý hai yêu cầu riêng biệt.

Sau đó, ta áp dụng chiến lược của Test Set 1 hai lần: một lần cho các ràng buộc tiền tố (sửa thuật toán để so sánh các tiền tố thay vì các hậu tố), và một lần cho các ràng buộc hậu tố. Nếu có mâu thuẫn thì không tồn tại đáp án. Nếu không, ta nối hai kết quả lại để thu được một đáp án hợp lệ và chắc chắn đủ ngắn, vì độ dài của nó nhiều nhất là \(99+99\) ký tự. Dấu sao duy nhất của mỗi mẫu có thể khớp với toàn bộ phần được thêm vào giữa tiền tố và hậu tố.

Test Set 3

Ta có thể tổng quát hóa ý tưởng trên thành lời giải cho Test Set 3. Mỗi mẫu \(p\) trong Test Set 3 cũng quy định một tiền tố của từ được xuất ra (phần tiền tố của \(p\) cho đến trước dấu sao đầu tiên) và một hậu tố của từ được xuất ra (phần hậu tố của \(p\) kể từ sau dấu sao cuối cùng). Nếu cho phép tiền tố và hậu tố rỗng, ta thu được đúng một tiền tố và một hậu tố cho mỗi mẫu. Ta có thể xử lý chúng giống như trong Test Set 2 để thu được tiền tố \(P\) và hậu tố \(S\) của kết quả, miễn là không phát hiện khác biệt ở một trong hai giai đoạn.

Tuy nhiên, với các mẫu có nhiều hơn một dấu sao, ta còn có thể gặp phần giữa, tạo ra một loại yêu cầu mới. Giả sử ta phân tích các phần nằm giữa những dấu sao của một mẫu sao cho \(X\) là tiền tố trước dấu sao đầu tiên, \(Y\) là hậu tố sau dấu sao cuối cùng, còn \(M_1, M_2, \ldots, M_k\) lần lượt là các chuỗi nằm giữa các dấu sao. Sau khi kiểm tra như trước rằng \(X\) là tiền tố của \(P\) và \(Y\) là hậu tố của \(S\), điều duy nhất còn phải bảo đảm là mẫu gồm \(M_1\), rồi dấu *, rồi \(M_2\), ..., rồi dấu * và \(M_k\) xuất hiện ở đâu đó trong từ kết quả, nằm hoàn toàn giữa \(P\) và \(S\).

Ta gọi \(M_1M_2\ldots M_k\) — tức phần nằm giữa dấu sao đầu tiên và dấu sao cuối cùng sau khi xóa mọi dấu sao khác — là từ giữa. Nếu bảo đảm từ giữa của một mẫu xuất hiện trong từ kết quả ở bên ngoài \(P\) và \(S\), ta sẽ thỏa mãn yêu cầu bổ sung đó. Vì vậy, ta có thể dựng một kết quả hợp lệ đầy đủ bằng cách bắt đầu với \(P\), sau đó thêm từ giữa của mọi mẫu theo thứ tự bất kỳ, rồi nối \(S\) vào cuối. Cần xử lý đúng những mẫu chỉ có một dấu sao hoặc chỉ có các dấu sao liên tiếp bằng cách coi từ giữa của chúng là chuỗi rỗng.

Cách dựng này đúng vì với từng mẫu, các đoạn \(M_1,M_2,\ldots,M_k\) xuất hiện đúng thứ tự trong từ giữa của chính mẫu đó; mọi phần xen giữa, kể cả từ giữa của các mẫu khác, đều có thể được các dấu sao hấp thụ. Do đó thứ tự nối các từ giữa là tùy ý.

Mỗi từ giữa có nhiều nhất \(98\) ký tự, còn tiền tố và hậu tố mỗi phần có nhiều nhất \(99\) ký tự. Vì thế, kết quả được dựng theo cách này có độ dài không quá \(99 \times 2 + 50 \times 98\), nằm trong giới hạn \(10^4\).

Độ phức tạp

Gọi \(C\) là tổng độ dài của tất cả các mẫu trong một bộ test. Việc tách mẫu, kiểm tra tiền tố và hậu tố, rồi ghép các từ giữa có thể thực hiện trong \(O(C)\) thời gian và dùng \(O(C)\) bộ nhớ.

Nguồn

Phần phân tích này được dịch đầy đủ từ lời giải chính thức của Google Code Jam 2020, Vòng 1A — Pattern Matching.