COMPRESS - Nén xâu
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift
Cho một xâu ~S~ chỉ gồm các kí tự latin in thường. Người ta tiến hành nén xâu ~S~ như sau:
- Chọn ra một xâu ~T~ có độ dài ngắn nhất có thể và chọn một số nguyên ~K~, sao cho khi viết xâu ~T~ lặp lại ~K~ lần, ta thu được xâu ~S~.
- Ghép nối ~K~ và ~T~, ta thu được xâu nén của ~S~.
Ví dụ:
- Với ~S =~
abcabcthì ~T =~abc, ~K = 2~ nên xâu nén của ~S~ là2abc - Với ~S =~
aaaathì ~T =~a, ~K = 4~ nên xâu nén của ~S~ là4a - Với ~S =~
freecontestthì ~T =~freecontest, ~K = 1~ nên xâu nén của ~S~ là1freecontest
Hãy cho biết xâu nén của ~S~.
Input
- Gồm một dòng duy nhất chứa xâu ~S~ độ dài không vượt quá ~1000~.
Output
- In ra xâu nén của xâu ~S~.
Sample
Input #1
abcabc
Output #1
2abc
Input #2
aaaa
Output #2
4a
Input #3
freecontest
Output #3
1freecontest
Problem source: Kc97ble - Free Contest
Bình luận
khó nhỉ
ý tưởng của mình như sau , mình sẽ duyệt độ dài chuỗi con : int len từ 1 đến (n-1) Nếu n%len==0 (n là độ dài xâu vào) thì sẽ kiểm tra 1 thằng gốc là tách từ chuỗi ban đầu từ vị trí 0 đến len rồi duyệt từ len đến vị trí 2*len , nếu tạo ra được thằng chuỗi con giống gốc thì trả về (n/len)+gốc. Thoát khỏi vòng lặp len thì trả về 1+chuỗi ban đầu =>AC hết nhénhé