หา index i ที่ prefix S1 และ suffix S2 ต่อกันได้ Palindrome (Python)

โจทย์: สตริง S1, S2 ความยาวเท่ากัน หา i ที่ S1[0..i] + S2[i+1..n-1] เป็น palindrome ไม่ได้ → -1

ตัวอย่าง: S1="pqrsu", S2="wxyqp" → i=1: "pq" + "ypq" = "pqyqp" (palindrome)

อัลกอริทึม Brute Force O(n²)

1. วน i จาก 0 ถึง n-1
2. สร้าง prefix = S1[0..i]
3. สร้าง suffix = S2[i+1..n-1]
4. ตรวจสอบ prefix+suffix เป็น palindrome หรือไม่

ตัวอย่างโค้ด

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

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

print(find_index("pqrsu", "wxyqp"))  # 1

ผลลัพธ์

1

สรุป: Brute force O(n²) เพราะสร้างสตริงและตรวจสอบ palindrome ทุก i สำหรับ n ใหญ่ ควรใช้ rolling hash หรือ Manacher's algorithm optimize