Bài toán tự nhiên gồm hai phần: tính số chuối tối đa cần mang và tính kỳ vọng số chuối phải trả.

Số chuối tối đa

Ví dụ từ mục tiêu \(X=\texttt{ABACABA}\). Để tạo chuỗi dài \(S\) chứa nhiều bản sao \(X\) nhất, trước hết đặt \(X\) ở đầu chuỗi. Sau đó, muốn thêm nhiều bản nhất thì phải chồng mỗi bản mới lên bản trước càng nhiều càng tốt.

Trong ví dụ, ta có thể chồng lên chữ A cuối và thêm BACABA, nhưng tốt hơn là chồng lên ABA rồi chỉ thêm CABA để có bản thứ hai. Vì \(L\) nhỏ, có thể thử mọi độ dài chồng lấn và kiểm tra. Cũng có thể tính trong thời gian tuyến tính bằng giai đoạn khởi tạo của thuật toán Knuth–Morris–Pratt.

Nếu độ dài chồng lấn lớn nhất là \(O\), số bản sao tối đa đặt được là

Nếu từ mục tiêu chứa một chữ không có trên bàn phím, không thể tạo bản sao nào và cả số tối đa lẫn kỳ vọng đều bằng 0.

Số chuối kỳ vọng

Trước hết tính xác suất \(P\) để từ mục tiêu xuất hiện ở một vị trí cố định. Nó bằng tích xác suất gõ đúng từng chữ; xác suất đúng một chữ là tỷ lệ số phím mang chữ đó:

Theo tính tuyến tính của kỳ vọng, kỳ vọng số bản sao chỉ là \(P\) nhân với số vị trí từ có thể bắt đầu, tức \(S-L+1\). Đây là tính chất rất tiện: ta không phải xử lý việc xuất hiện ở một vị trí và ở một vị trí chồng lấn là hai sự kiện không độc lập.

Đáp án cuối cùng là số bản sao tối đa trừ kỳ vọng số bản sao.

Mã tham khảo Python

# Find the maximum amount of overlap. We can just try
# every possible amount and check which ones work.
def max_overlap(t):
  for i in range(1, len(t)):
    if t[i:] == t[0:len(t)-i]:
      return len(t) - i
  return 0

# Returns the probability of the target word
# occurring at a fixed place.
def probability(target, keyboard):
  P = 1.0
  # Compute the product of the probabilities 
  # for each letter of the word being correct.
  for i in range(len(target)):
    # The probability for a single letter being correct
    # is the fraction of keys which are that letter.
    C = keyboard.count(target[i])
    P = P * C / len(keyboard);
  return P

for tc in range(input()):
  K, L, S = map(int, raw_input().split(' '))
  keyboard = raw_input()
  target = raw_input()
  res = 0
  P = probability(target, keyboard)
  if P > 0:
    O = max_overlap(target)
    max_copies = 1.0 + (S-L) / (L-O)
    min_copies = P * (S-L+1)
    res = max_copies - min_copies
  print("Case #%d: %f" % (tc + 1, res))

Lời giải C++ của Klockan trên bảng điểm cũng dùng cách tiếp cận này.

Một cách quy hoạch động khác

Có thể dùng DP cho cả hai phần với \(O(LS)\) trạng thái. Trạng thái gồm số ký tự đã gõ và số ký tự lớn nhất của tiền tố từ mục tiêu hiện đang khớp; giá trị lưu xác suất của trạng thái và số bản sao tối đa có thể đã tạo trên đường đến đó.

Mỗi khi vừa khớp toàn bộ từ, cộng xác suất tới trạng thái ấy vào kỳ vọng số bản sao và cập nhật số bản sao tối đa. linguo đã viết một lời giải Python kiểu này.

Dựa trên phân tích chính thức của Google Code Jam.