Tìm chỉ số i sao cho prefix S1 và suffix S2 tạo palindrome khi nối nhau trong Python

Cho hai chuỗi S1, S2 cùng độ dài, tìm chỉ số i sao cho S1[0..i] và S2[i+1..n-1] khi nối tạo thành palindrome. Không có thì trả về -1.

Ví dụ: S1="pqrsu", S2="wxyqp" → i=1 vì "pq" + "ypq" = "pqyqp" là palindrome.

Thuật toán O(n²)

1. Duyệt i từ 0 đến n-1.
2. Xây str = S1[0..i] và temp = S2[i+1..n-1].
3. Kiểm tra str + temp có phải palindrome không (so sánh với chuỗi đảo).
4. Trả về i đầu tiên thỏa mãn, hoặc -1.

Ví dụ code

def isPalindrome(s):
    return s == s[::-1]

def find_index(str1, str2):
    n = len(str1)
    s = ""
    for i in range(n):
        s += str1[i]
        temp = ""
        for j in range(i + 1, n):
            temp += str2[j]
        if isPalindrome(s + temp):
            return i
    return -1

str1 = "pqrsu"
str2 = "wxyqp"
print(find_index(str1, str2))

Input

"pqrsu", "wxyqp"

Output

1