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
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
-
3
VoBaThongL921
7:47 a.m. 7 Tháng 10, 2021
-
4
dattuan16_05_07
5:45 p.m. 23 Tháng 3, 2022
-
2
longkold00
8:37 a.m. 7 Tháng 10, 2021
5 bình luận nữaCông nhận anh Long mới học c++ mà ghê thiệt chớ:> Mà nghi anh học lâu rồi mà lừa em nha
idol của idol thì pro là đúng r mà 🙂
Ơ a nói thiệt mè 🙁 a mới học từ hồi thi thpt xong á