Rút gọn xâu
Xem PDF
Điểm:
100 (p)
Thời gian:
1.0s
Bộ nhớ:
640M
Input:
bàn phím
Output:
màn hình
Cho một xâu \(S\) chỉ gồm các chữ cái in thường. Cách mô tả rút gọn của xâu \(S\) như sau:
- Chọn ra một xâu \(X\) ngắn nhất có thể và một số nguyên dương \(K\), sao cho khi viết xâu \(X\) lặp lại \(K\) lần thì ta thu được xâu \(S\)
- Ghép \(K\) và \(X\), ta thu được xâu rút gọn của \(S\).
Ví dụ:
- Xâu rút gọn của “abababab” là “4ab”
- Xâu rút gọn của “aaa” là “3a”
- Xâu rút gọn của “abac” là “1abac”
Input
- Gồm một dòng duy nhất chứa xâu \(S\) có độ dài không quá \(1000\).
Output
- In ra xâu rút gọn của xâu \(S\).
Example
Test 1
Input
abababab Output
4abTest 2
Input
aaa Output
3aTest 3
Input
abac Output
1abac
Bình luận
include <bits/stdc++.h>
using namespace std;
long long a,b,c,d,m,x,ma,k,q,j,f;
string n,z,t,kq[1000000],ks[1000000];
int main()
{
cin>>n;
f=n.size()-1;
for(long long i=1;i<=n.size();i++)
{
t=n.substr(0,i);
z=n.substr(f,-i);
f--;
//cout<<t<<"---"<<z<<'\n';
if(t==z) {cout<<n.size()/i<<t; break;}
}
}
5 bình luận nữa