Tìm chỉ số i sao cho tiền tố S1 và hậu tố S2 đến i tạo thành palindrome khi nối nhau trong C++

Khái niệm

Cho hai chuỗi S1 và S2 cùng độ dài, tìm chỉ số i sao cho S1[0…i] và S2[i+1…n-1] khi nối nhau tạo thành palindrome. Nếu không tìm thấy chỉ số nào, in -1.

Đầu vào

S1 = “pqrsu”, S2 = “wxyqp”

Đầu ra

S1[0..1] = “pq”, S2[2..n-1] = “ypq”

S1 + S2 = “pqyqp” là palindrome.

Đầu vào

S1 = “pqrst”, S2 = “qprqz”

Đầu ra

-1

Phương pháp

Duyệt từ 0 đến n (độ dài chuỗi), sao chép ký tự thứ i từ S1 vào chuỗi khác (giả sử S).
Tạo chuỗi tạm temp, sao chép các ký tự của S2 từ chỉ số i+1 đến n.
Kiểm tra xem chuỗi (S + temp) có phải palindrome không.

Ví dụ

// C++ triển khai phương pháp
#include <bits/stdc++.h>
using namespace std;

// Hàm kiểm tra chuỗi palindrome
bool isPalindrome(string str){
    int i = 0;
    int b = str.length() - 1;
    while (i < b) {
        if (str[i] != str[b])
            return false;
        i++;
        b--;
    }
    return true;
}

// Hàm trả về chỉ số yêu cầu
int getIndex1(string S1, string S2, int n){
    string S = "";
    for (int i = 0; i < n; i++) {
        // Sao chép ký tự thứ i vào S
        S = S + S1[i];
        string temp = "";
        // Sao chép tất cả ký tự của S2 vào temp
        for (int b = i + 1; b < n; b++)
            temp += S2[b];
        // Kiểm tra palindrome
        if (isPalindrome(S + temp)) {
            return i;
        }
    }
    return -1;
}

// Chương trình chính
int main(){
    string S1 = "pqrsu", S2 = "wxyqp";
    int n = S1.length();
    cout << getIndex1(S1, S2, n);
    return 0;
}