Tạo palindrome
Xem PDF
Điểm:
300 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Cho một xâu \(s\). Cần thêm ít nhất bao nhiêu ký tự vào cuối xâu \(s\) để tạo thành một xâu đối xứng? In ra xâu đối xứng đó.
Input
- Dòng đầu tiên chứa một số nguyên dương \(t\), số truy vấn bạn phải trả lời \((1 \leq t \leq 100)\).
- \(t\) dòng tiếp theo, mỗi dòng chứa một xâu \(s\).
- Tổng độ dài các xâu \(s\) không vượt quá \(5 \times 10^5\).
Output
- Với mỗi truy vấn, in ra một dòng là xâu đối xứng tạo thành.
Example
Test 1
Input
4
aaaa
abba
amanaplanacanal
xyz Output
aaaa
abba
amanaplanacanalpanama
xyzyx
Bình luận
WA 1 test đau
mà nick bạn Long là gì thế
bạn kb zalo hay fb thế bạn Long
kb với mình ko bạn long
Sau đây mình sẽ trình bày ý tưởng bài toán bằng 2 con trỏ:
Gọi xâu ban đầu có độ dài s=> n=s.length(-1), ta đặt i=0, j=n và tạo 1 xâu a="";
Trong khi i<j ta thực hiện vòng lặp while. Nếu s[i]=s[j] gán j--, ngược lại ta kiểm tra xem xâu từ j->n có là xâu con của xâu từ 0->i hay không. nếu không, if(j!=n) {i--;}
j=n;
Khi vòng lặp kết thúc sẽ có 2 trường hợp xảy ra. if(i==j) a=s.substr(0,2*i-n); else a=s.substr(0,2*i-n-1); . Sau đó ta đảo ngược xâu a và in ra xâu s và a.
Dưới đây là phần code của mình
enter link description here
dạ có ai để lại hint cho người đi sau không ạ :< em làm bài này nhưng mà chỉ biết cách quy hoạch động thì dựng mảng 2 chiều và truy vết nhưng maxping thì độ dài chỉ tầm 1000 là căng ạ :<