بازگشت به عقب در رشته‌ها: پالیندروم‌ها
طولانی‌ترین زیررشته پالیندروم با روش توسعه از مرکز — O(n²) با شهود واضح و پیاده‌سازی تمیز
مسئله
طولانی‌ترین زیررشته پالیندروم را پیدا کنید: «babad» ← «bab» یا «aba». این مسئله کلاسیک، سه سطح راه‌حل دارد:
سطح ۱: وحشیانه O(n³)
همه زیررشته‌ها + بررسی پالیندروم بودن هر کدام. برای n=1000 یعنی میلیارد عملیات!
سطح ۲: برنامه‌نویسی پویا O(n²)
جدول dp[i][j] = آیا s[i..j] پالیندروم است؟ رابطه: s[i]==s[j] و dp[i+1][j-1]. حافظه O(n²).
سطح ۳: توسعه از مرکز O(n²) با O(1) حافظه ✓
بینش کلیدی: هر پالیندروم یک مرکز دارد که از آن دو طرف متقارن گسترش می‌یابد:
- مرکز تک‌کاراکتری: «aba» — n مرکز
- مرکز بین دو کاراکتر: «abba» — n−1 مرکز
- جمعاً 2n−1 مرکز ممکن!
الگوریتم: از هر مرکز، تا جایی که کاراکترها برابرند گسترش بده؛ بهترین را نگه دار.
مثال گام‌به‌گام
s = "babad"
مرکز 0 (b): "b" -> طول ۱
مرکز 1 (a): "aba" ✓ -> طول ۳!
مرکز 2 (b): "bab" ✓ -> طول ۳
مرکز 3 (a): "a"
مرکز 4 (d): "d"
مرکز بین‌ها: هیچ جفت متوالی برابر نیست
جواب: "aba" یا "bab" (طول ۳)مقایسه روش‌ها
| روش | زمان | حافظه |
|---|---|---|
| وحشیانه | O(n³) | O(1) |
| DP | O(n²) | O(n²) |
| توسعه از مرکز | O(n²) | O(1) ✓ |
| الگوریتم Manacher | O(n) | O(n) — پیشرفته |
نکته مصاحبه: «توسعه از مرکز» پاسخ مورد انتظار است — ساده، O(1) حافظه و پیاده‌سازی کوتاه. Manacher را فقط نام ببرید (O(n) اما پیچیده)!
جمع‌بندی
- هر پالیندروم از یک مرکز (تک یا بین دو کاراکتر) گسترش می‌یابد
- 2n−1 مرکز را امتحان کن؛ هر کدام حداکثر O(n)
- مجموع: O(n²) زمان، O(1) حافظه
- مسئله مرتبط: شمارش همه زیررشته‌های پالیندروم — همان گسترش!
این مبحث بخشی از دوره آموزش کامل الگوریتم‌ها است.