PVHOI 2.2 bài 5: Tiền tố chung dài nhất (70 điểm)

Xem dạng PDF

Gửi bài giải

Điểm: 1,20 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout

Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Pascal

Xét hai xâu kí tự bất kì ~a = a_1 a_2 \ldots a_m~ và ~b = b_1 b_2 \ldots b_n~. Ta nói độ dài tiền tố chung dài nhất của hai xâu ~a~ và ~b~ là ~l~ khi và chỉ khi:

  • ~l \leq m~ và ~l \leq n~.
  • Với mọi ~1 \leq i \leq l~, ta có ~a_i = b_i~.
  • ~l~ là số nguyên lớn nhất sao cho cả hai điều trên đều đúng.

Ví dụ, độ dài tiền tố chung dài nhất của hai xâu "gsts" và "gspvh" là ~2~, độ dài tiền tố chung dài nhất của hai xâu "iloveyou" và "iloveyoubabe" là ~8~, độ dài tiền tố chung dài nhất của hai xâu "com" và "tro" là ~0~.

Cho ~n~ xâu kí tự ~s_1, s_2, \ldots, s_n~ và một số nguyên ~k~. Bạn cần chọn ra ~k~ xâu trong số ~n~ xâu trên sao cho tổng độ dài tiền tố chung dài nhất của mọi cặp hai xâu được chọn là lớn nhất có thể. Nói cách khác, giả sử các xâu được chọn là ~x_1, x_2, \ldots, x_k~ và gọi ~lcp(u, v)~ là độ dài tiền tố chung dài nhất của hai xâu ~s_u~ và ~s_v~, bạn cần cực đại hóa giá trị sau: ~\sum_{i = 1}^{k} \sum_{j = i + 1}^{k} lcp(x_i, x_j)~.

Input

Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~ ~(1 \leq k \leq n \leq 5000)~.

Trong ~n~ dòng còn lại, dòng thứ ~i~ chứa xâu kí tự ~s_i~. Xâu kí tự này khác rỗng và chỉ gồm các chữ cái in thường.

Dữ liệu vào đảm bảo tổng độ dài của các xâu ~s_1, s_2, \ldots, s_n~ không quá ~4 \cdot 10^6~.

Output

In ra một số nguyên duy nhất là giá trị lớn nhất của biểu thức ở trên, là tổng của độ dài tiền tố chung dài nhất xét trên mọi cặp xâu kí tự được chọn.

Sắp tát

Bộ test của bài được chia làm các sắp tát như sau:

  • Sắp tát ~1~ (~10~ điểm): Tất cả các xâu chỉ gồm một loại ký tự. Cụ thể, các xâu ~s_i~ chỉ có thể là "a", "bb", hay "ccc" mà không thể là "ab" hay "cac".
  • Sắp tát ~2~ (~10~ điểm): ~k = n~
  • Sắp tát ~3~ (~10~ điểm): ~k = 3~
  • Sắp tát ~4~ (~10~ điểm): ~n \leq 20~
  • Sắp tát ~5~ (~15~ điểm): ~n \leq 500~ và độ dài mỗi xâu không quá ~500~.
  • Sắp tát ~6~ (~15~ điểm): Không có ràng buộc gì thêm.

Điểm tối đa của bài là ~70~ điểm.

Ví dụ

Input 1

7 3
diduduadi
duadidudi
dudua
dudu
didi
didudua
duadidu

Output 1

13

Input 2

5 3
pvhoi
tigersugar
gspvh
ndt
fos

Output 2

0

Giải thích

Trong ví dụ đầu tiên, phương án tối ưu là chọn ba xâu ~s_1~, ~s_5~ và ~s_6~. Khi đó:

  • ~lcp(1, 5) = 3~
  • ~lcp(1, 6) = 7~
  • ~lcp(5, 6) = 3~

Tổng độ dài tiền tố chung dài nhát của các cặp xâu được chọn là ~3 + 7 + 3 = 13~

Trong ví dụ thứ hai, hai xâu bất kì trong các xâu đã cho đều có độ dài tiền tố chung dài nhất bằng ~0~. Vì vậy, mọi cách chọn ~k~ xâu đều cho ra tổng độ dài tiền tố chung dài nhất là ~0~.


Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.