Xâu con tốt nhất
Đề bài
Mô tả
Cho một xâu . Gọi là vị trí bắt đầu của xâu con độ dài tốt nhất. Với hai xâu con và có cùng độ dài, xâu nào có thứ tự từ điển nhỏ hơn thì tốt hơn. Nếu hai xâu con giống nhau, xâu nào có vị trí bắt đầu nhỏ hơn thì tốt hơn.
Đặt . Nhiệm vụ của bạn là tính .
Dữ liệu vào
- Dòng đầu tiên chứa số bộ dữ liệu .
- Mỗi bộ dữ liệu là một dòng chứa một xâu .
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra trên một dòng.
Ràng buộc
- .
- .
- Tổng độ dài các xâu không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 apple banana abcdabcd |
15 36 36 |
Các vị trí được đánh số từ . Với "apple", xâu con tốt nhất của mọi độ dài đều bắt đầu ở vị trí , nên . Với "banana", với (ví dụ "ana" xuất hiện ở vị trí và , chọn vị trí nhỏ hơn) và với , nên . |
| 1 a |
1 | Chỉ có một xâu con độ dài , bắt đầu ở vị trí . |
Bình luận