Dizideki En Uzun Palindromik Alt Dizeyi Bulma (Java)
### Giriş
Bilgisayar bilimlerinde ve yazılım geliştirmede dize (string) manipülasyonu, birçok problemin temelini oluşturur. Bu problemlerden biri, verilen bir dize içindeki en uzun palindromik alt dizeyi (Longest Palindromic Substring – LPS) bulmaktır. Bu makalede, bu klasik problemi ele alacak, farklı algoritmik yaklaşımları Java dilinde kod örnekleriyle birlikte detaylı bir şekilde inceleyeceğiz.
Peki, “palindrom” nedir? Bir palindrom, tersten okunduğunda da aynı olan bir kelime, sayı, cümle veya dizedir. Örneğin, “madam”, “kayak”, “ana” veya “level” kelimeleri birer palindromdur. “Alt dize” ise, bir dizenin ardışık karakterlerinden oluşan bir bölümüdür. Örneğin, “banana” dizisinin alt dizeleri “ban”, “ana”, “nan” gibi birçok farklı kombinasyonu içerebilir. “Longest Palindromic Substring” problemi ise, verilen bir dizenin tüm alt dizeleri arasında palindrom olanların en uzununu bulmayı hedefler.
Bu problem, sadece akademik bir egzersiz olmanın ötesinde, biyoinformatik (DNA ve RNA dizisi analizi), metin işleme, veri sıkıştırma ve örüntü tanıma gibi çeşitli alanlarda pratik uygulamalara sahiptir. Farklı algoritmik yaklaşımlar, problemin karmaşıklığını anlamak ve verimli çözümler tasarlamak için önemli bir zemin sunar. Bu makalede, kaba kuvvet (brute-force) yönteminden başlayarak, merkezden genişletme (expand around center), dinamik programlama ve son olarak en verimli olan Manacher algoritmasına kadar çeşitli çözüm yollarını adım adım inceleyeceğiz.
### Problemin Tanımı ve Örnekler
Longest Palindromic Substring (LPS) problemi, matematiksel olarak şu şekilde tanımlanabilir: Verilen bir $S$ dizisi için, $S$’nin tüm alt dizeleri $S[i \dots j]$ arasından, tersten okunduğunda kendisine eşit olan (yani palindrom olan) ve $j-i+1$ uzunluğu maksimum olan alt dizeyi bulun. Eğer birden fazla en uzun palindromik alt dize varsa, herhangi birini döndürmek yeterlidir.
Örneklerle problemi daha iyi anlayalım:
1. Giriş: “babad”
* Çıkış: “bab” veya “aba”. Her ikisi de 3 karakter uzunluğundadır ve en uzun palindromdur.
2. Giriş: “cbbd”
* Çıkış: “bb”. 2 karakter uzunluğundadır.
3. Giriş: “a”
* Çıkış: “a”. 1 karakter uzunluğundadır.
4. Giriş: “ac”
* Çıkış: “a” veya “c”. Her ikisi de 1 karakter uzunluğundadır.
5. Giriş: “forgeeksskeegfor”
* Çıkış: “geeksskeeg”. 10 karakter uzunluğundadır.
Bu örnekler, farklı dize tipleri için problemin nasıl çalıştığını göstermektedir. Şimdi bu problemi çözmek için kullanabileceğimiz farklı algoritmik yaklaşımlara geçelim.
### Temel Yaklaşımlar
#### Brute-Force (Kaba Kuvvet) Yaklaşımı
Kaba kuvvet yaklaşımı, bir problemi çözmek için en basit ve en doğrudan yöntemdir. LPS probleminde, bu yaklaşım, verilen dizenin tüm olası alt dizelerini oluşturmayı, her bir alt dizenin palindrom olup olmadığını kontrol etmeyi ve bu süreçte bulunan en uzun palindromu takip etmeyi içerir.
Algoritma Adımları:
1. longestPalindrome adında boş bir dize tanımlayın.
2. Dizinin başlangıcından sonuna kadar i indeksini kullanarak tüm olası başlangıç noktalarını yineleyin.
3. Her i için, i‘den dizinin sonuna kadar j indeksini kullanarak tüm olası bitiş noktalarını yineleyin.
4. s[i...j] alt dizesini çıkarın.
5. Bu alt dizenin bir palindrom olup olmadığını kontrol edin. Bunu yapmak için, alt dizeyi tersten okuyup orijinaliyle karşılaştırabilir veya iki işaretçi (sol ve sağ) kullanarak merkeze doğru ilerleyebilirsiniz.
6. Eğer alt dize bir palindromsa ve longestPalindrome‘dan daha uzunsa, longestPalindrome‘ı bu yeni alt dize ile güncelleyin.
7. Tüm alt dizeler kontrol edildikten sonra, longestPalindrome sonucunu döndürün.
Uygulama Detayları ve Karmaşıklık Analizi:
Bu yaklaşım üç iç içe döngü gerektirir:
* Dış döngü i için $N$ iterasyon.
* İç döngü j için $N$ iterasyon.
* Palindrom kontrolü için (en kötü durumda) $N$ iterasyon.
Dolayısıyla, zaman karmaşıklığı $O(N^3)$’tür. $N$, giriş dizisinin uzunluğudur. Bu, büyük giriş dizileri için oldukça verimsizdir. Örneğin, 1000 karakterlik bir dize için $1000^3 = 1$ milyar işlem anlamına gelir ki bu kabul edilemez derecede yavaştır.
Alan karmaşıklığı ise, her seferinde bir alt dize oluşturmak için $O(N)$ ve longestPalindrome‘ı saklamak için $O(N)$ olduğundan, genel olarak $O(N)$’dir.
Java Kod Örneği:
public class LongestPalindromicSubstring {
// Yardımcı metot: Bir dizenin palindrom olup olmadığını kontrol eder
private boolean isPalindrome(String s) {
int left = 0;
int right = s.length() - 1;
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
// Kaba Kuvvet Yaklaşımı
public String longestPalindromeBruteForce(String s) {
if (s == null || s.length() < 1) {
return "";
}
String longestPalindrome = "";
for (int i = 0; i < s.length(); i++) {
for (int j = i; j < s.length(); j++) {
String sub = s.substring(i, j + 1);
if (isPalindrome(sub)) {
if (sub.length() > longestPalindrome.length()) {
longestPalindrome = sub;
}
}
}
}
return longestPalindrome;
}
// main metodu örnek kullanım için
public static void main(String[] args) {
LongestPalindromicSubstring solver = new LongestPalindromicSubstring();
System.out.println("Brute-Force:");
System.out.println("babad -> " + solver.longestPalindromeBruteForce("babad")); // bab veya aba
System.out.println("cbbd -> " + solver.longestPalindromeBruteForce("cbbd")); // bb
System.out.println("a -> " + solver.longestPalindromeBruteForce("a")); // a
System.out.println("ac -> " + solver.longestPalindromeBruteForce("ac")); // a
System.out.println("forgeeksskeegfor -> " + solver.longestPalindromeBruteForce("forgeeksskeegfor")); // geeksskeeg
}
}#### Merkezden Genişletme (Expand Around Center) Yaklaşımı
Kaba kuvvet yaklaşımının verimsizliğini gidermek için daha akıllı bir yaklaşım geliştirebiliriz. Bir palindromun merkezine göre simetrik olduğu gözleminden yola çıkarak, her olası merkezi ele alıp bu merkezden dışarı doğru genişleyebiliriz.
Palindromların iki tür merkezi olabilir:
1. Tek uzunluklu palindromlar: Tek bir karakter merkezlidir (örneğin, “racecar” için ‘e’).
2. Çift uzunluklu palindromlar: İki karakterin arası merkezlidir (örneğin, “abba” için ‘bb’ arasındaki boşluk).
Bu iki durumu ele almak için, her karakteri (tek uzunluklu palindromlar için) ve her iki karakter arasındaki boşluğu (çift uzunluklu palindromlar için) merkez olarak kabul edip genişleme yapabiliriz.
Algoritma Adımları:
1. start ve end adında iki değişken tanımlayın, bunlar en uzun palindromun başlangıç ve bitiş indekslerini tutacaktır. Başlangıçta 0 olarak ayarlanabilirler.
2. Dizinin her karakteri için i indeksini yineleyin (0’dan s.length()-1‘e kadar).
3. Her i için, iki ayrı genişletme işlemi yapın:
* expandAroundCenter(s, i, i): Tek uzunluklu palindromlar için (merkez tek bir karakterdir).
* expandAroundCenter(s, i, i + 1): Çift uzunluklu palindromlar için (merkez iki karakter arasındadır).
4. expandAroundCenter metodu, verilen left ve right indekslerinden başlayarak dışarı doğru genişler. Genişleme, s.charAt(left) == s.charAt(right) olduğu sürece devam eder. Her adımda left azalır ve right artar.
5. Genişleme durduğunda, right - left - 1 bize bulunan palindromun uzunluğunu verir.
6. Eğer bu uzunluk, şu ana kadar bulunan en uzun palindromun (end - start + 1) uzunluğundan büyükse, start ve end değerlerini güncelleyin.
7. Tüm merkezler kontrol edildikten sonra, s.substring(start, end + 1) sonucunu döndürün.
Uygulama Detayları ve Karmaşıklık Analizi:
* Döngü i için $N$ kez çalışır.
* Her i için, expandAroundCenter metodu en kötü durumda $N/2$ kez genişleme yapar. Bu, her expandAroundCenter çağrısı için $O(N)$ zaman karmaşıklığı anlamına gelir.
İki expandAroundCenter çağrısı olduğu için, toplam zaman karmaşıklığı $O(N N) = O(N^2)$ olur.
* Alan karmaşıklığı ise, sadece birkaç değişken kullanıldığı için $O(1)$’dir (dize manipülasyonları hariç, çünkü substring metodu yeni dize oluşturur ama bu genellikle algoritmanın çekirdeği olarak sayılmaz). Bu, kaba kuvvet yaklaşımına göre önemli bir iyileşmedir.
Java Kod Örneği:
public class LongestPalindromicSubstring {
private int maxLen = 0;
private int start = 0;
// Merkezden Genişletme Yardımcı Metodu
private void expandAroundCenter(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
// Döngü bittiğinde, left ve right bir adım fazla gitmiştir.
// Palindromun gerçek başlangıcı left + 1, bitişi right - 1'dir.
// Uzunluk: (right - 1) - (left + 1) + 1 = right - left - 1
if (maxLen < right - left - 1) {
start = left + 1;
maxLen = right - left - 1;
}
}
// Merkezden Genişletme Yaklaşımı
public String longestPalindromeExpandAroundCenter(String s) {
if (s == null || s.length() < 1) {
return "";
}
for (int i = 0; i < s.length(); i++) {
// Tek uzunluklu palindromlar için (merkez: s[i])
expandAroundCenter(s, i, i);
// Çift uzunluklu palindromlar için (merkez: s[i] ve s[i+1] arası)
expandAroundCenter(s, i, i + 1);
}
return s.substring(start, start + maxLen);
}
// main metodu örnek kullanım için
public static void main(String[] args) {
LongestPalindromicSubstring solver = new LongestPalindromicSubstring();
System.out.println("Expand Around Center:");
System.out.println("babad -> " + solver.longestPalindromeExpandAroundCenter("babad")); // bab veya aba
System.out.println("cbbd -> " + solver.longestPalindromeExpandAroundCenter("cbbd")); // bb
System.out.println("a -> " + solver.longestPalindromeExpandAroundCenter("a")); // a
System.out.println("ac -> " + solver.longestPalindromeExpandAroundCenter("ac")); // a
System.out.println("forgeeksskeegfor -> " + solver.longestPalindromeExpandAroundCenter("forgeeksskeegfor")); // geeksskeeg
}
}### Dinamik Programlama (Dynamic Programming) Yaklaşımı
Dinamik programlama (DP), bir problemi daha küçük, örtüşen alt problemlere bölerek ve bu alt problemlerin çözümlerini depolayarak karmaşık problemleri çözmek için kullanılan güçlü bir tekniktir. LPS probleminde, bir alt dizenin palindrom olup olmadığını belirlemek için, daha küçük alt dizelerin palindrom olup olmadığını bilmek bize yardımcı olabilir.
Temel Fikir:
dp[i][j] adında bir boolean matrisi oluşturalım. dp[i][j], s[i...j] alt dizesinin bir palindrom olup olmadığını true/false olarak tutacaktır.
Tekrarlayan İlişki (Recurrence Relation):
s[i...j] alt dizesinin bir palindrom olması için iki koşulun sağlanması gerekir:
1. s[i] karakteri ile s[j] karakteri birbirine eşit olmalıdır.
2. s[i+1...j-1] alt dizesi de bir palindrom olmalıdır.
Bu durumda, dp[i][j] = (s.charAt(i) == s.charAt(j)) && dp[i+1][j-1] olur.
Temel Durumlar (Base Cases):
* Tek karakterli alt dizeler: Her tek karakterli alt dize bir palindromdur. Yani, dp[i][i] = true tüm i‘ler için.
* İki karakterli alt dizeler: s[i...i+1] bir palindromdur eğer s.charAt(i) == s.charAt(i+1) ise. Yani, dp[i][i+1] = (s.charAt(i) == s.charAt(i+1)) tüm i‘ler için.
Tablo Doldurma Sırası:
dp[i+1][j-1] değerine ihtiyaç duyduğumuz için, matrisi doldururken alt dizelerin uzunluğuna göre artan sırada ilerlememiz gerekir. Yani, önce uzunluğu 1 olan alt dizeler, sonra 2 olanlar, sonra 3 olanlar vb.
Algoritma Adımları:
1. N boyutunda bir dize için N x N boyutunda dp boolean matrisi oluşturun.
2. longestPalindrome ve maxLength değişkenlerini başlatın (örneğin, ilk karakteri başlangıç palindromu olarak alabilirsiniz).
3. Uzunluk 1: Tüm dp[i][i] değerlerini true olarak ayarlayın.
4. Uzunluk 2: i‘den N-2‘ye kadar döngü yapın. Eğer s.charAt(i) == s.charAt(i+1) ise, dp[i][i+1] = true olarak ayarlayın ve maxLength ile longestPalindrome‘ı güncelleyin.
5. Uzunluk 3’ten N’e kadar: len (alt dize uzunluğu) 3’ten N‘e kadar döngü yapın.
* Her len için, i (başlangıç indeksi) 0’dan N - len‘e kadar döngü yapın.
* j (bitiş indeksi) i + len - 1 olarak hesaplayın.
* Eğer s.charAt(i) == s.charAt(j) ve dp[i+1][j-1] true ise, dp[i][j] = true olarak ayarlayın.
* Eğer dp[i][j] true ise ve len şu anki maxLength‘ten büyükse, maxLength ve longestPalindrome‘ı güncelleyin.
6. Son olarak, longestPalindrome‘ı döndürün.
Uygulama Detayları ve Karmaşıklık Analizi:
* DP tablosunu doldurmak için iç içe üç döngü vardır: len (uzunluk), i (başlangıç indeksi) ve j (bitiş indeksi). Ancak j i ve len‘e bağlıdır. Temel olarak, $N^2$ hücreyi doldururuz ve her hücreyi doldurmak sabit zaman alır.
* Zaman karmaşıklığı $O(N^2)$’dir.
* Alan karmaşıklığı ise N x N boyutundaki dp matrisi için $O(N^2)$’dir.
Bu yaklaşım, merkezden genişletme yaklaşımıyla aynı zaman karmaşıklığına sahip olsa da, daha fazla alan kullanır. Ancak, dinamik programlama kavramını anlamak için iyi bir örnektir.
Java Kod Örneği:
public class LongestPalindromicSubstring {
// Dinamik Programlama Yaklaşımı
public String longestPalindromeDP(String s) {
if (s == null || s.length() < 1) {
return "";
}
int n = s.length();
boolean[][] dp = new boolean[n][n]; // dp[i][j] true ise s[i...j] bir palindromdur
String longestPalindrome = "";
int maxLength = 0;
// Tek karakterli alt dizeler her zaman palindromdur (uzunluk = 1)
for (int i = 0; i < n; i++) {
dp[i][i] = true;
if (1 > maxLength) {
maxLength = 1;
longestPalindrome = s.substring(i, i + 1);
}
}
// İki karakterli alt dizeler (uzunluk = 2)
for (int i = 0; i < n - 1; i++) {
if (s.charAt(i) == s.charAt(i + 1)) {
dp[i][i + 1] = true;
if (2 > maxLength) {
maxLength = 2;
longestPalindrome = s.substring(i, i + 2);
}
}
}
// Uzunluk 3'ten N'e kadar olan alt dizeler
for (int len = 3; len <= n; len++) {
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1; // Bitiş indeksi
// s[i...j] bir palindrom mu?
// s[i] == s[j] OLMALI VE s[i+1...j-1] BİR PALİNDROM OLMALI
if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {
dp[i][j] = true;
if (len > maxLength) {
maxLength = len;
longestPalindrome = s.substring(i, j + 1);
}
}
}
}
return longestPalindrome;
}
// main metodu örnek kullanım için
public static void main(String[] args) {
LongestPalindromicSubstring solver = new LongestPalindromicSubstring();
System.out.println("Dynamic Programming:");
System.out.println("babad -> " + solver.longestPalindromeDP("babad")); // bab veya aba
System.out.println("cbbd -> " + solver.longestPalindromeDP("cbbd")); // bb
System.out.println("a -> " + solver.longestPalindromeDP("a")); // a
System.out.println("ac -> " + solver.longestPalindromeDP("ac")); // a
System.out.println("forgeeksskeegfor -> " + solver.longestPalindromeDP("forgeeksskeegfor")); // geeksskeeg
}
}### Manacher Algoritması (Gelişmiş ve Optimal Yaklaşım)
Şimdiye kadar incelediğimiz algoritmalar $O(N^2)$ zaman karmaşıklığına sahipti. Ancak, “Longest Palindromic Substring” problemi için $O(N)$ zaman karmaşıklığına sahip doğrusal bir çözüm mevcuttur: Manacher Algoritması. Bu algoritma, daha önce hesaplanmış palindrom bilgilerini akıllıca kullanarak gereksiz tekrarlayan kontrolleri önler.
Neden O(N) karmaşıklığına ihtiyaç duyarız?
$N^2$ algoritmalar genellikle $N$’in 1000-5000 aralığında olduğu durumlar için kabul edilebilir olabilir. Ancak, $N$ 10.000 veya daha büyük olduğunda $N^2$ çözümler çok yavaşlar. O(N) çözümler, bu tür büyük veri setlerinde bile hızlı yanıt süreleri sağlar ve genellikle daha sofistike problem çözme tekniklerinin bir göstergesidir.
Ana Fikir:
Manacher algoritmasının temel fikri, bir palindromun simetrisinden yararlanmaktır. Bir palindromun bir bölümünü zaten biliyorsak, onun simetrik karşılığının da bir palindrom olacağını varsayabiliriz. Bu bilgi, yeni palindromları keşfederken başlangıç noktamızı optimize etmemizi sağlar.
Ön İşleme (Preprocessing):
Manacher algoritması, tek ve çift uzunluklu palindromları aynı şekilde ele almak için giriş dizisini dönüştürür. Her karakter arasına ve dizenin başına/sonuna özel bir karakter (örneğin ‘#’) eklenir. Bu, tüm palindromların yeni dizede tek uzunluklu olmasını sağlar.
Örnek:
* “babad” -> “#b#a#b#a#d#” (uzunluk 5 -> 11)
* “cbbd” -> “#c#b#b#d#” (uzunluk 4 -> 9)
Bu dönüşüm, her palindromun artık bir merkezi karaktere sahip olmasını sağlar, bu da algoritmayı basitleştirir.
Algoritma Adımları:
1. Dizeyi Dönüştür: Yukarıda açıklandığı gibi, giriş dizisini özel karakterlerle genişletin. Dönüştürülmüş dizeye T diyelim. T‘nin uzunluğu 2*N + 1 olacaktır.
2. P Dizisi: P[i] adında bir dizi oluşturun. P[i], T[i] merkezli en uzun palindromun yarı uzunluğunu (veya yarı çapını) tutacaktır. Örneğin, T[i] merkezli palindrom T[i-P[i]...i+P[i]] ise, P[i] bu palindromun i‘den ne kadar uzandığını gösterir (kendi dahil).
3. C (Center) ve R (Right Boundary):
* C: Şu ana kadar bulunan ve en sağa uzanan palindromun merkezi.
* R: C merkezli palindromun sağ sınırı (C + P[C]).
4. İterasyon: T dizisi üzerinde i (0’dan T.length()-1‘e kadar) ile döngü yapın.
Simetrik İndeks (i_mirror): i_mirror = 2C - i. Bu, i‘nin C‘ye göre simetrik indeksidir.
* Minimum Palindrom Yarıçapı: i‘deki palindromun en az min(P[i_mirror], R - i) kadar olacağını biliyoruz. Eğer i R‘nin içindeyse, P[i]‘nin başlangıç değeri bu minimum değerdir. Eğer i R‘nin dışındaysa, P[i] başlangıçta 0’dır.
* Genişletme: T[i - P[i] - 1] == T[i + P[i] + 1] olduğu sürece P[i]‘yi artırın. (Sınır kontrollerini unutmayın: i - P[i] - 1 >= 0 ve i + P[i] + 1 < T.length()).
* C ve R Güncellemesi: Eğer i + P[i] değeri R'den büyükse (yani yeni bulunan palindrom daha sağa uzanıyorsa), C'yi i'ye ve R'yi i + P[i]'ye güncelleyin.
5. En Uzun Palindromu Bul: P dizisindeki en büyük değeri (maxLen) bulun. Bu maxLen, dönüştürülmüş dizedeki en uzun palindromun yarıçapıdır.
* En uzun palindromun merkezi maxCenter olacaktır.
* Orijinal dizedeki başlangıç indeksi (maxCenter - maxLen) / 2 olacaktır.
* Orijinal dizedeki uzunluk maxLen olacaktır.
6. Sonucu döndürün: s.substring(start, start + maxLen).
Uygulama Detayları ve Karmaşıklık Analizi:
* Dizeyi dönüştürmek $O(N)$ zaman alır.
* Ana döngü $N'$ (dönüştürülmüş dizenin uzunluğu, yaklaşık $2N$) kez çalışır.
* P[i]'nin her artırılması (genişletme adımı) toplamda N' kez gerçekleşir. Bu, amortize edilmiş analize göre her karakterin sadece sabit sayıda kez ziyaret edildiği anlamına gelir.
* Zaman karmaşıklığı $O(N)$'dir.
* Alan karmaşıklığı P dizisi ve dönüştürülmüş dize için $O(N)$'dir.
Manacher algoritması, teorik olarak en verimli çözümdür. Ancak, uygulaması diğer yaklaşımlara göre daha karmaşıktır.
Java Kod Örneği:
public class LongestPalindromicSubstring {
// Manacher Algoritması
public String longestPalindromeManacher(String s) {
if (s == null || s.length() == 0) {
return "";
}
// 1. Dizeyi Ön İşleme (Preprocessing)
// Her karakter arasına ve başına/sonuna '#' ekleyerek
// tüm palindromları tek uzunluklu hale getiriyoruz.
StringBuilder t = new StringBuilder();
t.append('$'); // Başlangıç işareti (sınır kontrolü için)
t.append('#');
for (char c : s.toCharArray()) {
t.append(c);
t.append('#');
}
t.append('@'); // Bitiş işareti (sınır kontrolü için)
char[] T = t.toString().toCharArray(); // Dönüştürülmüş dize
int n = T.length;
int[] P = new int[n]; // P[i]: T[i] merkezli palindromun yarıçapı
int C = 0; // Center: En sağa uzanan palindromun merkezi
int R = 0; // Right boundary: C merkezli palindromun sağ sınırı (C + P[C])
int maxLen = 0; // En uzun palindromun yarıçapı
int centerIndex = 0; // En uzun palindromun merkez indeksi
for (int i = 1; i < n - 1; i++) { // '$' ve '@' işaretlerini atlıyoruz
// i_mirror: i'nin C'ye göre simetrik indeksi
int i_mirror = 2 * C - i;
// Eğer i, R'nin içindeyse, P[i] en az min(P[i_mirror], R - i) olabilir
// Değilse, P[i] başlangıçta 0'dır (tek karakterli palindrom)
if (R > i) {
P[i] = Math.min(R - i, P[i_mirror]);
} else {
P[i] = 0;
}
// Merkezden genişle
// T[i - P[i] - 1] == T[i + P[i] + 1] olduğu sürece P[i]'yi artır
while (T[i + P[i] + 1] == T[i - P[i] - 1]) {
P[i]++;
}
// Eğer yeni bulunan palindrom R'yi aşıyorsa, C ve R'yi güncelle
if (i + P[i] > R) {
C = i;
R = i + P[i];
}
// En uzun palindromu güncelle
if (P[i] > maxLen) {
maxLen = P[i];
centerIndex = i;
}
}
// Orijinal dizedeki en uzun palindromu çıkar
// centerIndex: Dönüştürülmüş dizedeki merkezin indeksi
// maxLen: Dönüştürülmüş dizedeki palindromun yarıçapı
// Orijinal dizedeki başlangıç indeksi: (centerIndex - maxLen) / 2
// Orijinal dizedeki uzunluk: maxLen
int startIndex = (centerIndex - maxLen) / 2;
return s.substring(startIndex, startIndex + maxLen);
}
// main metodu örnek kullanım için
public static void main(String[] args) {
LongestPalindromicSubstring solver = new LongestPalindromicSubstring();
System.out.println("Manacher Algorithm:");
System.out.println("babad -> " + solver.longestPalindromeManacher("babad")); // bab
System.out.println("cbbd -> " + solver.longestPalindromeManacher("cbbd")); // bb
System.out.println("a -> " + solver.longestPalindromeManacher("a")); // a
System.out.println("ac -> " + solver.longestPalindromeManacher("ac")); // a
System.out.println("forgeeksskeegfor -> " + solver.longestPalindromeManacher("forgeeksskeegfor")); // geeksskeeg
System.out.println("racecar -> " + solver.longestPalindromeManacher("racecar")); // racecar
System.out.println("abba -> " + solver.longestPalindromeManacher("abba")); // abba
}
}### Yaklaşımların Karşılaştırılması
Farklı algoritmik yaklaşımları bir tablo halinde karşılaştırmak, her birinin avantajlarını ve dezavantajlarını net bir şekilde görmemizi sağlar:
| Yaklaşım | Zaman Karmaşıklığı | Alan Karmaşıklığı | Uygulama Kolaylığı | Açıklama |
| :-------------------- | :----------------- | :---------------- | :----------------- | :---------------------------------------------------------------------- |
| Brute-Force | $O(N^3)$ | $O(N)$ | Çok Kolay | Tüm alt dizeleri kontrol eder, en yavaş yöntem. |
| Merkezden Genişletme | $O(N^2)$ | $O(1)$ | Orta | Her olası merkezden dışarı doğru genişler, pratikte iyi performans. |
| Dinamik Programlama | $O(N^2)$ | $O(N^2)$ | Orta | Alt problem çözümlerini depolayarak tekrar hesaplamaları önler. |
| Manacher Algoritması | $O(N)$ | $O(N)$ | Zor | En verimli yöntem, özel ön işleme ve simetri kullanır. |
Hangi Yaklaşım Ne Zaman Kullanılmalı?
* Brute-Force: Sadece çok küçük N değerleri için veya bir kavramı hızlıca test etmek için kullanılır. Genellikle pratik uygulamalar için önerilmez.
* Merkezden Genişletme: N^2 çözümlerin yeterli olduğu çoğu pratik senaryo için iyi bir seçenektir. Uygulaması nispeten kolaydır ve $O(1)$ alan karmaşıklığı ile hafıza dostudur.
* Dinamik Programlama: N^2 çözümlerin yeterli olduğu ve DP kavramının anlaşılmasının istendiği durumlarda kullanılabilir. Ancak, $O(N^2)$ alan karmaşıklığı nedeniyle hafıza kısıtlamaları olan durumlarda dikkatli olunmalıdır.
* Manacher Algoritması: N çok büyük olduğunda ve en yüksek performansın gerektiği durumlarda tercih edilir. Uygulaması karmaşık olduğu için, sadece performans kritik durumlarda veya algoritmik bir meydan okuma olarak düşünülmelidir.
### Uygulama Alanları
Longest Palindromic Substring problemi ve onun çözümleri, çeşitli gerçek dünya senaryolarında uygulama bulur:
* Biyoinformatik: DNA ve RNA dizileri genellikle palindromik veya ters tekrarlayan bölgeler içerir. Bu bölgelerin tespiti, genetik düzenleme, protein bağlama siteleri ve hastalık teşhisi gibi biyolojik süreçleri anlamada kritik öneme sahiptir.
* Metin İşleme ve Dize Eşleştirme: Büyük metin veri kümelerinde palindromik desenleri bulmak, doğal dil işleme (NLP) ve metin madenciliği uygulamalarında kullanılabilir. Örneğin, metinlerdeki belirli yapıları veya anlamsal özelliklere sahip bölgeleri tanımlamak.
* Veri Sıkıştırma: Palindromik alt dizelerin tespiti, veri sıkıştırma algoritmalarında tekrarlayan desenleri bulmak ve bunları daha verimli bir şekilde temsil etmek için bir ön adım olabilir.
* Algoritma Tasarımı Prensip Örneği: Bu problem, dinamik programlama, açgözlü algoritmalar ve doğrusal zaman algoritmaları gibi farklı algoritma tasarım paradigmalarını öğretmek ve karşılaştırmak için mükemmel bir örnektir. Öğrencilerin ve geliştiricilerin algoritmik düşünme becerilerini geliştirmelerine yardımcı olur.
* Kriptografi: Belirli dize desenlerinin analizi, kriptografik algoritmaların zayıflıklarını veya güçlü yönlerini anlamak için kullanılabilir.
### Sonuç
Bu makalede, verilen bir dize içindeki en uzun palindromik alt dizeyi bulma problemine odaklandık. Kaba kuvvet, merkezden genişletme, dinamik programlama ve Manacher algoritması gibi dört farklı yaklaşımı detaylı bir şekilde inceledik. Her bir algoritmanın çalışma prensibini, zaman ve alan karmaşıklığını ve Java dilinde uygulanışını örnek kodlarla birlikte sunduk.
Gördüğümüz gibi, kaba kuvvet yaklaşımı basit olmasına rağmen yüksek karmaşıklığı nedeniyle pratik değildir. Merkezden genişletme ve dinamik programlama yaklaşımları $O(N^2)$ zaman karmaşıklığına sahip olup, birçok senaryo için kabul edilebilir performans sunar. Ancak, büyük veri kümeleri için en optimal çözüm, $O(N)$ zaman karmaşıklığına sahip olan Manacher algoritmasıdır. Manacher algoritması, ön işleme ve simetri özelliklerini akıllıca kullanarak tekrarlayan hesaplamalardan kaçınır ve doğrusal zamanda çözüm sunar.
Bu problemin çözümü, algoritmik düşünmenin ve farklı problem çözme stratejilerinin önemini vurgular. Algoritmaların karmaşıklığını anlamak ve bir problem için en uygun çözümü seçmek, verimli ve ölçeklenebilir yazılım geliştirmek için temel bir beceridir. Longest Palindromic Substring gibi klasik problemler, bu becerileri geliştirmek ve teorik bilgiyi pratik uygulamalara dönüştürmek için değerli bir zemin sağlar.