Tạo palindrome

Xem PDF
Tác giả:
cuom1999
Dạng bài
Đ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


  • 6
    longkold00    7:29 p.m. 6 Tháng 10, 2021 ← chỉnh sửa 3

    Sau đây mình sẽ trình bày ý tưởng bài toán bằng 2 con trỏ:

    1. 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="";

    2. 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;

    3. 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

      Cô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


      • 4
        dattuan16_05_07    5:45 p.m. 23 Tháng 3, 2022

        idol của idol thì pro là đúng r mà 🙂


        • 2
          longkold00    8:37 a.m. 7 Tháng 10, 2021

          Ơ a nói thiệt mè 🙁 a mới học từ hồi thi thpt xong á

        5 bình luận nữa