\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{orange}{\text{Hướng dẫn}}\)

• Gọi \(s\) là xâu được nhập

• Gọi \(x\) là kí tự được thêm

• Gọi \(c\) là kí tự đầu xâu \(s\)

• Mục tiêu: Kiểm tra \(s\) là xâu đối xứng, hoặc \(s + x\) là xâu đối xứng

• Nhận xét: Nếu kí tự \(x \neq c\) thì \(s + x\) không thể là xâu đối xứng

Ta chỉ cần kiểm tra tính đối xứng của \(s\) hoặc \(s + c\) thì in ra "YES"

\(\color{goldenrod}{\text{Tiếp cận}}\)

• Để kiểm tra xâu đối xứng có nhiều cách

Cách 1: Tạo xâu \(t = s\) và đảo ngược nó. Nếu \(s = t\) thì \(s\) đối xứng

Cách 2: Nếu \(s_l = s_r\ \forall\) cặp \((l, r)\) là 2 vị trí đối xứng trên xâu

\(\color{green}{\text{Code tham khảo }}\): Cách 1, Giải trực tiếp, cài đặt

\(^{^{\color{purple}{\text{Độ phức tạp : }} O(q)\ \color{purple}{\text{thời gian}}\ ||\ O(q + \Sigma(|s|))\ \color{purple}{\text{bộ nhớ}}}}\)

#include <algorithm>
#include <iostream>

using namespace std;

bool isPalind(const string &s)
{
    string t = s;
    reverse(t.begin(), t.end());
    return (t == s);
}

int main()
{
    int q;
    cin >> q;

    while (q-->0)
    {
        string s;
        cin >> s;

        if (isPalind(s) || isPalind(s + s.front()))
            cout << "YES\n";
        else 
            cout << "NO\n";
    }

    return 0;
}

\(\color{green}{\text{Code tham khảo }}\): Cách 2, Giải trực tiếp, cài đặt

\(^{^{\color{purple}{\text{Độ phức tạp : }} O(q)\ \color{purple}{\text{thời gian}}\ ||\ O(q + \Sigma(|s|))\ \color{purple}{\text{bộ nhớ}}}}\)

#include <algorithm>
#include <iostream>

using namespace std;

bool isPalind(const string &s)
{
    int l = 0;
    int r = int(s.size()) - 1;
    for (; l < r; ++l, --r)
        if (s[l] != s[r])
            return false;

    return true;
}

int main()
{
    int q;
    cin >> q;

    while (q-->0)
    {
        string s;
        cin >> s;

        if (isPalind(s) || isPalind(s + s.front()))
            cout << "YES\n";
        else 
            cout << "NO\n";
    }

    return 0;
}