Nội dung Bài tập
- Mã:
- PSTR
- Tên:
- tính hàm chuỗi
- Dạng thi:
- oi
- Thang điểm:
- 10 điểm
- Giới hạn thời gian:
- 1 giây
- Giới hạn bộ nhớ:
- 256 MB
- Được tạo bởi:
- kydq
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:
p(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 p(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 Output
Giải thích:
p(‘a’) = 1 * 6 = 6
p(‘aa’) = 2 * 5 = 10
p(‘aaa’) = 3 * 4 = 12
p(‘aaaa’) = 4 * 3 = 12
p(‘aaaaa’) = 5 * 2 = 10
p(‘aaaaaa’) = 6 * 1 = 6
Xâu ‘aaa’ và ‘aaaa’ có cùng giá trị p(s), nhưng ‘aaa’ < ‘aaaa’ nên ta lấy ‘aaa’ làm kết quả.
Theme :
Mời bạn soạn code
Ai có thể xem bài này :
Thông tin
Phần thảo luận
#include <iostream>using namespace std;struct ps { int tu, mau; &...