FSTR - Tính hàm
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: yurilover172

Cho xâu ký tự S. Với mọi xâu con s của S, tính giá trị hàm f sau:

f(s) = |s| * (số lần s xuất hiện trong S)

(|s| là độ dài xâu s)

Tìm xâu con s của S sao cho f(s) là lớn nhất. Nếu có nhiều xâu s như vậy thì in ra xâu có thứ tự từ điển nhỏ nhất.

Input: Gồm 2 dòng:

- Dòng 1: Chứa số nguyên duy nhất n là độ dài xâu S (1 ≤ n ≤ 105)

- Dòng 2: Chứa xâu ký tự S (chỉ gồm các ký tự in được từ 0x20 tới 0x7E).

Output:

- Gồm 1 dòng duy nhất chứa xâu kết quả.

Ví dụ

  • input
    6
    aaaaaa
    output
    aaa

Giải thích:

f(‘a’)      = 1 * 6 = 6

f(‘aa’)     = 2 * 5 = 10

f(‘aaa’)    = 3 * 4 = 12

f(‘aaaa’)   = 4 * 3 = 12

f(‘aaaaa’)  = 5 * 2 = 10

f(‘aaaaaa’) = 6 * 1 = 6

Xâu ‘aaa’‘aaaa’ có cùng giá trị f(s), nhưng ‘aaa’ < ‘aaaa’ nên ta lấy ‘aaa’ làm kết quả.

Back to Top