### Giri\u015f<\/p>\n
Bilgisayar bilimlerinde ve yaz\u0131l\u0131m geli\u015ftirmede dize (string) manip\u00fclasyonu, bir\u00e7ok problemin temelini olu\u015fturur. Bu problemlerden biri, verilen bir dize i\u00e7indeki en uzun palindromik alt dizeyi (Longest Palindromic Substring – LPS) bulmakt\u0131r. Bu makalede, bu klasik problemi ele alacak, farkl\u0131 algoritmik yakla\u015f\u0131mlar\u0131 Java dilinde kod \u00f6rnekleriyle birlikte detayl\u0131 bir \u015fekilde inceleyece\u011fiz.<\/p>\n
Peki, “palindrom” nedir? Bir palindrom, tersten okundu\u011funda da ayn\u0131 olan bir kelime, say\u0131, c\u00fcmle veya dizedir. \u00d6rne\u011fin, “madam”, “kayak”, “ana” veya “level” kelimeleri birer palindromdur. “Alt dize” ise, bir dizenin ard\u0131\u015f\u0131k karakterlerinden olu\u015fan bir b\u00f6l\u00fcm\u00fcd\u00fcr. \u00d6rne\u011fin, “banana” dizisinin alt dizeleri “ban”, “ana”, “nan” gibi bir\u00e7ok farkl\u0131 kombinasyonu i\u00e7erebilir. “Longest Palindromic Substring” problemi ise, verilen bir dizenin t\u00fcm alt dizeleri aras\u0131nda palindrom olanlar\u0131n en uzununu bulmay\u0131 hedefler.<\/p>\n
Bu problem, sadece akademik bir egzersiz olman\u0131n \u00f6tesinde, biyoinformatik (DNA ve RNA dizisi analizi), metin i\u015fleme, veri s\u0131k\u0131\u015ft\u0131rma ve \u00f6r\u00fcnt\u00fc tan\u0131ma gibi \u00e7e\u015fitli alanlarda pratik uygulamalara sahiptir. Farkl\u0131 algoritmik yakla\u015f\u0131mlar, problemin karma\u015f\u0131kl\u0131\u011f\u0131n\u0131 anlamak ve verimli \u00e7\u00f6z\u00fcmler tasarlamak i\u00e7in \u00f6nemli bir zemin sunar. Bu makalede, kaba kuvvet (brute-force) y\u00f6nteminden ba\u015flayarak, merkezden geni\u015fletme (expand around center), dinamik programlama ve son olarak en verimli olan Manacher algoritmas\u0131na kadar \u00e7e\u015fitli \u00e7\u00f6z\u00fcm yollar\u0131n\u0131 ad\u0131m ad\u0131m inceleyece\u011fiz.<\/p>\n
### Problemin Tan\u0131m\u0131 ve \u00d6rnekler<\/p>\n
Longest Palindromic Substring (LPS) problemi, matematiksel olarak \u015fu \u015fekilde tan\u0131mlanabilir: Verilen bir $S$ dizisi i\u00e7in, $S$’nin t\u00fcm alt dizeleri $S[i \\dots j]$ aras\u0131ndan, tersten okundu\u011funda kendisine e\u015fit olan (yani palindrom olan) ve $j-i+1$ uzunlu\u011fu maksimum olan alt dizeyi bulun. E\u011fer birden fazla en uzun palindromik alt dize varsa, herhangi birini d\u00f6nd\u00fcrmek yeterlidir.<\/p>\n
\u00d6rneklerle problemi daha iyi anlayal\u0131m:<\/p>\n
1. Giri\u015f:<\/strong> “babad” 2. Giri\u015f:<\/strong> “cbbd” 3. Giri\u015f:<\/strong> “a” 4. Giri\u015f:<\/strong> “ac” 5. Giri\u015f:<\/strong> “forgeeksskeegfor” Bu \u00f6rnekler, farkl\u0131 dize tipleri i\u00e7in problemin nas\u0131l \u00e7al\u0131\u015ft\u0131\u011f\u0131n\u0131 g\u00f6stermektedir. \u015eimdi bu problemi \u00e7\u00f6zmek i\u00e7in kullanabilece\u011fimiz farkl\u0131 algoritmik yakla\u015f\u0131mlara ge\u00e7elim.<\/p>\n ### Temel Yakla\u015f\u0131mlar<\/p>\n #### Brute-Force (Kaba Kuvvet) Yakla\u015f\u0131m\u0131<\/p>\n Kaba kuvvet yakla\u015f\u0131m\u0131, bir problemi \u00e7\u00f6zmek i\u00e7in en basit ve en do\u011frudan y\u00f6ntemdir. LPS probleminde, bu yakla\u015f\u0131m, verilen dizenin t\u00fcm olas\u0131 alt dizelerini olu\u015fturmay\u0131, her bir alt dizenin palindrom olup olmad\u0131\u011f\u0131n\u0131 kontrol etmeyi ve bu s\u00fcre\u00e7te bulunan en uzun palindromu takip etmeyi i\u00e7erir.<\/p>\n Algoritma Ad\u0131mlar\u0131:<\/strong><\/p>\n 1. Uygulama Detaylar\u0131 ve Karma\u015f\u0131kl\u0131k Analizi:<\/strong><\/p>\n Bu yakla\u015f\u0131m \u00fc\u00e7 i\u00e7 i\u00e7e d\u00f6ng\u00fc gerektirir: Dolay\u0131s\u0131yla, zaman karma\u015f\u0131kl\u0131\u011f\u0131 $O(N^3)$’t\u00fcr. $N$, giri\u015f dizisinin uzunlu\u011fudur. Bu, b\u00fcy\u00fck giri\u015f dizileri i\u00e7in olduk\u00e7a verimsizdir. \u00d6rne\u011fin, 1000 karakterlik bir dize i\u00e7in $1000^3 = 1$ milyar i\u015flem anlam\u0131na gelir ki bu kabul edilemez derecede yava\u015ft\u0131r.<\/p>\n Alan karma\u015f\u0131kl\u0131\u011f\u0131 ise, her seferinde bir alt dize olu\u015fturmak i\u00e7in $O(N)$ ve Java Kod \u00d6rne\u011fi:<\/strong><\/p>\n #### Merkezden Geni\u015fletme (Expand Around Center) Yakla\u015f\u0131m\u0131<\/p>\n Kaba kuvvet yakla\u015f\u0131m\u0131n\u0131n verimsizli\u011fini gidermek i\u00e7in daha ak\u0131ll\u0131 bir yakla\u015f\u0131m geli\u015ftirebiliriz. Bir palindromun merkezine g\u00f6re simetrik oldu\u011fu g\u00f6zleminden yola \u00e7\u0131karak, her olas\u0131 merkezi ele al\u0131p bu merkezden d\u0131\u015far\u0131 do\u011fru geni\u015fleyebiliriz.<\/p>\n Palindromlar\u0131n iki t\u00fcr merkezi olabilir: Bu iki durumu ele almak i\u00e7in, her karakteri (tek uzunluklu palindromlar i\u00e7in) ve her iki karakter aras\u0131ndaki bo\u015flu\u011fu (\u00e7ift uzunluklu palindromlar i\u00e7in) merkez olarak kabul edip geni\u015fleme yapabiliriz.<\/p>\n Algoritma Ad\u0131mlar\u0131:<\/strong><\/p>\n 1. Uygulama Detaylar\u0131 ve Karma\u015f\u0131kl\u0131k Analizi:<\/strong><\/p>\n * D\u00f6ng\u00fc Java Kod \u00d6rne\u011fi:<\/strong><\/p>\n ### Dinamik Programlama (Dynamic Programming) Yakla\u015f\u0131m\u0131<\/p>\n Dinamik programlama (DP), bir problemi daha k\u00fc\u00e7\u00fck, \u00f6rt\u00fc\u015fen alt problemlere b\u00f6lerek ve bu alt problemlerin \u00e7\u00f6z\u00fcmlerini depolayarak karma\u015f\u0131k problemleri \u00e7\u00f6zmek i\u00e7in kullan\u0131lan g\u00fc\u00e7l\u00fc bir tekniktir. LPS probleminde, bir alt dizenin palindrom olup olmad\u0131\u011f\u0131n\u0131 belirlemek i\u00e7in, daha k\u00fc\u00e7\u00fck alt dizelerin palindrom olup olmad\u0131\u011f\u0131n\u0131 bilmek bize yard\u0131mc\u0131 olabilir.<\/p>\n Temel Fikir:<\/strong><\/p>\n Tekrarlayan \u0130li\u015fki (Recurrence Relation):<\/strong><\/p>\n Bu durumda, Temel Durumlar (Base Cases):<\/strong><\/p>\n * Tek karakterli alt dizeler:<\/strong> Her tek karakterli alt dize bir palindromdur. Yani, Tablo Doldurma S\u0131ras\u0131:<\/strong><\/p>\n Algoritma Ad\u0131mlar\u0131:<\/strong><\/p>\n 1. Uygulama Detaylar\u0131 ve Karma\u015f\u0131kl\u0131k Analizi:<\/strong><\/p>\n * DP tablosunu doldurmak i\u00e7in i\u00e7 i\u00e7e \u00fc\u00e7 d\u00f6ng\u00fc vard\u0131r: Bu yakla\u015f\u0131m, merkezden geni\u015fletme yakla\u015f\u0131m\u0131yla ayn\u0131 zaman karma\u015f\u0131kl\u0131\u011f\u0131na sahip olsa da, daha fazla alan kullan\u0131r. Ancak, dinamik programlama kavram\u0131n\u0131 anlamak i\u00e7in iyi bir \u00f6rnektir.<\/p>\n Java Kod \u00d6rne\u011fi:<\/strong><\/p>\n ### Manacher Algoritmas\u0131 (Geli\u015fmi\u015f ve Optimal Yakla\u015f\u0131m)<\/p>\n \u015eimdiye kadar inceledi\u011fimiz algoritmalar $O(N^2)$ zaman karma\u015f\u0131kl\u0131\u011f\u0131na sahipti. Ancak, “Longest Palindromic Substring” problemi i\u00e7in $O(N)$ zaman karma\u015f\u0131kl\u0131\u011f\u0131na sahip do\u011frusal bir \u00e7\u00f6z\u00fcm mevcuttur: Manacher Algoritmas\u0131. Bu algoritma, daha \u00f6nce hesaplanm\u0131\u015f palindrom bilgilerini ak\u0131ll\u0131ca kullanarak gereksiz tekrarlayan kontrolleri \u00f6nler.<\/p>\n Neden O(N) karma\u015f\u0131kl\u0131\u011f\u0131na ihtiya\u00e7 duyar\u0131z?<\/strong><\/p>\n $N^2$ algoritmalar genellikle $N$’in 1000-5000 aral\u0131\u011f\u0131nda oldu\u011fu durumlar i\u00e7in kabul edilebilir olabilir. Ancak, $N$ 10.000 veya daha b\u00fcy\u00fck oldu\u011funda $N^2$ \u00e7\u00f6z\u00fcmler \u00e7ok yava\u015flar. O(N) \u00e7\u00f6z\u00fcmler, bu t\u00fcr b\u00fcy\u00fck veri setlerinde bile h\u0131zl\u0131 yan\u0131t s\u00fcreleri sa\u011flar ve genellikle daha sofistike problem \u00e7\u00f6zme tekniklerinin bir g\u00f6stergesidir.<\/p>\n Ana Fikir:<\/strong><\/p>\n Manacher algoritmas\u0131n\u0131n temel fikri, bir palindromun simetrisinden yararlanmakt\u0131r. Bir palindromun bir b\u00f6l\u00fcm\u00fcn\u00fc zaten biliyorsak, onun simetrik kar\u015f\u0131l\u0131\u011f\u0131n\u0131n da bir palindrom olaca\u011f\u0131n\u0131 varsayabiliriz. Bu bilgi, yeni palindromlar\u0131 ke\u015ffederken ba\u015flang\u0131\u00e7 noktam\u0131z\u0131 optimize etmemizi sa\u011flar.<\/p>\n \u00d6n \u0130\u015fleme (Preprocessing):<\/strong><\/p>\n Manacher algoritmas\u0131, tek ve \u00e7ift uzunluklu palindromlar\u0131 ayn\u0131 \u015fekilde ele almak i\u00e7in giri\u015f dizisini d\u00f6n\u00fc\u015ft\u00fcr\u00fcr. Her karakter aras\u0131na ve dizenin ba\u015f\u0131na\/sonuna \u00f6zel bir karakter (\u00f6rne\u011fin ‘#’) eklenir. Bu, t\u00fcm palindromlar\u0131n yeni dizede tek uzunluklu olmas\u0131n\u0131 sa\u011flar.<\/p>\n \u00d6rnek: Bu d\u00f6n\u00fc\u015f\u00fcm, her palindromun art\u0131k bir merkezi karaktere sahip olmas\u0131n\u0131 sa\u011flar, bu da algoritmay\u0131 basitle\u015ftirir.<\/p>\n Algoritma Ad\u0131mlar\u0131:<\/strong><\/p>\n 1. Dizeyi D\u00f6n\u00fc\u015ft\u00fcr:<\/strong> Yukar\u0131da a\u00e7\u0131kland\u0131\u011f\u0131 gibi, giri\u015f dizisini \u00f6zel karakterlerle geni\u015fletin. D\u00f6n\u00fc\u015ft\u00fcr\u00fclm\u00fc\u015f dizeye 4. \u0130terasyon:<\/strong> 5. En Uzun Palindromu Bul:<\/strong> 6. Sonucu d\u00f6nd\u00fcr\u00fcn: Uygulama Detaylar\u0131 ve Karma\u015f\u0131kl\u0131k Analizi:<\/strong><\/p>\n * Dizeyi d\u00f6n\u00fc\u015ft\u00fcrmek $O(N)$ zaman al\u0131r. Manacher algoritmas\u0131, teorik olarak en verimli \u00e7\u00f6z\u00fcmd\u00fcr. Ancak, uygulamas\u0131 di\u011fer yakla\u015f\u0131mlara g\u00f6re daha karma\u015f\u0131kt\u0131r.<\/p>\n Java Kod \u00d6rne\u011fi:<\/strong><\/p>\n ### Yakla\u015f\u0131mlar\u0131n Kar\u015f\u0131la\u015ft\u0131r\u0131lmas\u0131<\/p>\n Farkl\u0131 algoritmik yakla\u015f\u0131mlar\u0131 bir tablo halinde kar\u015f\u0131la\u015ft\u0131rmak, her birinin avantajlar\u0131n\u0131 ve dezavantajlar\u0131n\u0131 net bir \u015fekilde g\u00f6rmemizi sa\u011flar:<\/p>\n | Yakla\u015f\u0131m | Zaman Karma\u015f\u0131kl\u0131\u011f\u0131 | Alan Karma\u015f\u0131kl\u0131\u011f\u0131 | Uygulama Kolayl\u0131\u011f\u0131 | A\u00e7\u0131klama | Hangi Yakla\u015f\u0131m Ne Zaman Kullan\u0131lmal\u0131?<\/strong><\/p>\n * Brute-Force:<\/strong> Sadece \u00e7ok k\u00fc\u00e7\u00fck
\n * \u00c7\u0131k\u0131\u015f:<\/strong> “bab” veya “aba”. Her ikisi de 3 karakter uzunlu\u011fundad\u0131r ve en uzun palindromdur.<\/p>\n
\n * \u00c7\u0131k\u0131\u015f:<\/strong> “bb”. 2 karakter uzunlu\u011fundad\u0131r.<\/p>\n
\n * \u00c7\u0131k\u0131\u015f:<\/strong> “a”. 1 karakter uzunlu\u011fundad\u0131r.<\/p>\n
\n * \u00c7\u0131k\u0131\u015f:<\/strong> “a” veya “c”. Her ikisi de 1 karakter uzunlu\u011fundad\u0131r.<\/p>\n
\n * \u00c7\u0131k\u0131\u015f:<\/strong> “geeksskeeg”. 10 karakter uzunlu\u011fundad\u0131r.<\/p>\nlongestPalindrome<\/code> ad\u0131nda bo\u015f bir dize tan\u0131mlay\u0131n.
\n2. Dizinin ba\u015flang\u0131c\u0131ndan sonuna kadar i<\/code> indeksini kullanarak t\u00fcm olas\u0131 ba\u015flang\u0131\u00e7 noktalar\u0131n\u0131 yineleyin.
\n3. Her i<\/code> i\u00e7in, i<\/code>‘den dizinin sonuna kadar j<\/code> indeksini kullanarak t\u00fcm olas\u0131 biti\u015f noktalar\u0131n\u0131 yineleyin.
\n4. s[i...j]<\/code> alt dizesini \u00e7\u0131kar\u0131n.
\n5. Bu alt dizenin bir palindrom olup olmad\u0131\u011f\u0131n\u0131 kontrol edin. Bunu yapmak i\u00e7in, alt dizeyi tersten okuyup orijinaliyle kar\u015f\u0131la\u015ft\u0131rabilir veya iki i\u015faret\u00e7i (sol ve sa\u011f) kullanarak merkeze do\u011fru ilerleyebilirsiniz.
\n6. E\u011fer alt dize bir palindromsa ve longestPalindrome<\/code>‘dan daha uzunsa, longestPalindrome<\/code>‘\u0131 bu yeni alt dize ile g\u00fcncelleyin.
\n7. T\u00fcm alt dizeler kontrol edildikten sonra, longestPalindrome<\/code> sonucunu d\u00f6nd\u00fcr\u00fcn.<\/p>\n
\n* D\u0131\u015f d\u00f6ng\u00fc i<\/code> i\u00e7in $N$ iterasyon.
\n* \u0130\u00e7 d\u00f6ng\u00fc j<\/code> i\u00e7in $N$ iterasyon.
\n* Palindrom kontrol\u00fc i\u00e7in (en k\u00f6t\u00fc durumda) $N$ iterasyon.<\/p>\nlongestPalindrome<\/code>‘\u0131 saklamak i\u00e7in $O(N)$ oldu\u011fundan, genel olarak $O(N)$’dir.<\/p>\npublic class LongestPalindromicSubstring {\n\n \/\/ Yard\u0131mc\u0131 metot: Bir dizenin palindrom olup olmad\u0131\u011f\u0131n\u0131 kontrol eder\n private boolean isPalindrome(String s) {\n int left = 0;\n int right = s.length() - 1;\n while (left < right) {\n if (s.charAt(left) != s.charAt(right)) {\n return false;\n }\n left++;\n right--;\n }\n return true;\n }\n\n \/\/ Kaba Kuvvet Yakla\u015f\u0131m\u0131\n public String longestPalindromeBruteForce(String s) {\n if (s == null || s.length() < 1) {\n return \"\";\n }\n\n String longestPalindrome = \"\";\n for (int i = 0; i < s.length(); i++) {\n for (int j = i; j < s.length(); j++) {\n String sub = s.substring(i, j + 1);\n if (isPalindrome(sub)) {\n if (sub.length() > longestPalindrome.length()) {\n longestPalindrome = sub;\n }\n }\n }\n }\n return longestPalindrome;\n }\n\n \/\/ main metodu \u00f6rnek kullan\u0131m i\u00e7in\n public static void main(String[] args) {\n LongestPalindromicSubstring solver = new LongestPalindromicSubstring();\n\n System.out.println(\"Brute-Force:\");\n System.out.println(\"babad -> \" + solver.longestPalindromeBruteForce(\"babad\")); \/\/ bab veya aba\n System.out.println(\"cbbd -> \" + solver.longestPalindromeBruteForce(\"cbbd\")); \/\/ bb\n System.out.println(\"a -> \" + solver.longestPalindromeBruteForce(\"a\")); \/\/ a\n System.out.println(\"ac -> \" + solver.longestPalindromeBruteForce(\"ac\")); \/\/ a\n System.out.println(\"forgeeksskeegfor -> \" + solver.longestPalindromeBruteForce(\"forgeeksskeegfor\")); \/\/ geeksskeeg\n }\n}<\/code><\/pre>\n
\n1. Tek uzunluklu palindromlar:<\/strong> Tek bir karakter merkezlidir (\u00f6rne\u011fin, “racecar” i\u00e7in ‘e’).
\n2. \u00c7ift uzunluklu palindromlar:<\/strong> \u0130ki karakterin aras\u0131 merkezlidir (\u00f6rne\u011fin, “abba” i\u00e7in ‘bb’ aras\u0131ndaki bo\u015fluk).<\/p>\nstart<\/code> ve end<\/code> ad\u0131nda iki de\u011fi\u015fken tan\u0131mlay\u0131n, bunlar en uzun palindromun ba\u015flang\u0131\u00e7 ve biti\u015f indekslerini tutacakt\u0131r. Ba\u015flang\u0131\u00e7ta 0 olarak ayarlanabilirler.
\n2. Dizinin her karakteri i\u00e7in i<\/code> indeksini yineleyin (0’dan s.length()-1<\/code>‘e kadar).
\n3. Her i<\/code> i\u00e7in, iki ayr\u0131 geni\u015fletme i\u015flemi yap\u0131n:
\n * expandAroundCenter(s, i, i)<\/code>: Tek uzunluklu palindromlar i\u00e7in (merkez tek bir karakterdir).
\n * expandAroundCenter(s, i, i + 1)<\/code>: \u00c7ift uzunluklu palindromlar i\u00e7in (merkez iki karakter aras\u0131ndad\u0131r).
\n4. expandAroundCenter<\/code> metodu, verilen left<\/code> ve right<\/code> indekslerinden ba\u015flayarak d\u0131\u015far\u0131 do\u011fru geni\u015fler. Geni\u015fleme, s.charAt(left) == s.charAt(right)<\/code> oldu\u011fu s\u00fcrece devam eder. Her ad\u0131mda left<\/code> azal\u0131r ve right<\/code> artar.
\n5. Geni\u015fleme durdu\u011funda, right - left - 1<\/code> bize bulunan palindromun uzunlu\u011funu verir.
\n6. E\u011fer bu uzunluk, \u015fu ana kadar bulunan en uzun palindromun (end - start + 1<\/code>) uzunlu\u011fundan b\u00fcy\u00fckse, start<\/code> ve end<\/code> de\u011ferlerini g\u00fcncelleyin.
\n7. T\u00fcm merkezler kontrol edildikten sonra, s.substring(start, end + 1)<\/code> sonucunu d\u00f6nd\u00fcr\u00fcn.<\/p>\ni<\/code> i\u00e7in $N$ kez \u00e7al\u0131\u015f\u0131r.
\n* Her i<\/code> i\u00e7in, expandAroundCenter<\/code> metodu en k\u00f6t\u00fc durumda $N\/2$ kez geni\u015fleme yapar. Bu, her expandAroundCenter<\/code> \u00e7a\u011fr\u0131s\u0131 i\u00e7in $O(N)$ zaman karma\u015f\u0131kl\u0131\u011f\u0131 anlam\u0131na gelir.
\n \u0130ki expandAroundCenter<\/code> \u00e7a\u011fr\u0131s\u0131 oldu\u011fu i\u00e7in, toplam zaman karma\u015f\u0131kl\u0131\u011f\u0131 $O(N <\/em> N) = O(N^2)$ olur.
\n* Alan karma\u015f\u0131kl\u0131\u011f\u0131 ise, sadece birka\u00e7 de\u011fi\u015fken kullan\u0131ld\u0131\u011f\u0131 i\u00e7in $O(1)$’dir (dize manip\u00fclasyonlar\u0131 hari\u00e7, \u00e7\u00fcnk\u00fc substring<\/code> metodu yeni dize olu\u015fturur ama bu genellikle algoritman\u0131n \u00e7ekirde\u011fi olarak say\u0131lmaz). Bu, kaba kuvvet yakla\u015f\u0131m\u0131na g\u00f6re \u00f6nemli bir iyile\u015fmedir.<\/p>\npublic class LongestPalindromicSubstring {\n\n private int maxLen = 0;\n private int start = 0;\n\n \/\/ Merkezden Geni\u015fletme Yard\u0131mc\u0131 Metodu\n private void expandAroundCenter(String s, int left, int right) {\n while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {\n left--;\n right++;\n }\n \/\/ D\u00f6ng\u00fc bitti\u011finde, left ve right bir ad\u0131m fazla gitmi\u015ftir.\n \/\/ Palindromun ger\u00e7ek ba\u015flang\u0131c\u0131 left + 1, biti\u015fi right - 1'dir.\n \/\/ Uzunluk: (right - 1) - (left + 1) + 1 = right - left - 1\n if (maxLen < right - left - 1) {\n start = left + 1;\n maxLen = right - left - 1;\n }\n }\n\n \/\/ Merkezden Geni\u015fletme Yakla\u015f\u0131m\u0131\n public String longestPalindromeExpandAroundCenter(String s) {\n if (s == null || s.length() < 1) {\n return \"\";\n }\n\n for (int i = 0; i < s.length(); i++) {\n \/\/ Tek uzunluklu palindromlar i\u00e7in (merkez: s[i])\n expandAroundCenter(s, i, i);\n \/\/ \u00c7ift uzunluklu palindromlar i\u00e7in (merkez: s[i] ve s[i+1] aras\u0131)\n expandAroundCenter(s, i, i + 1);\n }\n\n return s.substring(start, start + maxLen);\n }\n\n \/\/ main metodu \u00f6rnek kullan\u0131m i\u00e7in\n public static void main(String[] args) {\n LongestPalindromicSubstring solver = new LongestPalindromicSubstring();\n\n System.out.println(\"Expand Around Center:\");\n System.out.println(\"babad -> \" + solver.longestPalindromeExpandAroundCenter(\"babad\")); \/\/ bab veya aba\n System.out.println(\"cbbd -> \" + solver.longestPalindromeExpandAroundCenter(\"cbbd\")); \/\/ bb\n System.out.println(\"a -> \" + solver.longestPalindromeExpandAroundCenter(\"a\")); \/\/ a\n System.out.println(\"ac -> \" + solver.longestPalindromeExpandAroundCenter(\"ac\")); \/\/ a\n System.out.println(\"forgeeksskeegfor -> \" + solver.longestPalindromeExpandAroundCenter(\"forgeeksskeegfor\")); \/\/ geeksskeeg\n }\n}<\/code><\/pre>\ndp[i][j]<\/code> ad\u0131nda bir boolean matrisi olu\u015ftural\u0131m. dp[i][j]<\/code>, s[i...j]<\/code> alt dizesinin bir palindrom olup olmad\u0131\u011f\u0131n\u0131 true\/false olarak tutacakt\u0131r.<\/p>\ns[i...j]<\/code> alt dizesinin bir palindrom olmas\u0131 i\u00e7in iki ko\u015fulun sa\u011flanmas\u0131 gerekir:
\n1. s[i]<\/code> karakteri ile s[j]<\/code> karakteri birbirine e\u015fit olmal\u0131d\u0131r.
\n2. s[i+1...j-1]<\/code> alt dizesi de bir palindrom olmal\u0131d\u0131r.<\/p>\ndp[i][j] = (s.charAt(i) == s.charAt(j)) && dp[i+1][j-1]<\/code> olur.<\/p>\ndp[i][i] = true<\/code> t\u00fcm i<\/code>‘ler i\u00e7in.
\n* \u0130ki karakterli alt dizeler:<\/strong> s[i...i+1]<\/code> bir palindromdur e\u011fer s.charAt(i) == s.charAt(i+1)<\/code> ise. Yani, dp[i][i+1] = (s.charAt(i) == s.charAt(i+1))<\/code> t\u00fcm i<\/code>‘ler i\u00e7in.<\/p>\ndp[i+1][j-1]<\/code> de\u011ferine ihtiya\u00e7 duydu\u011fumuz i\u00e7in, matrisi doldururken alt dizelerin uzunlu\u011funa g\u00f6re artan s\u0131rada ilerlememiz gerekir. Yani, \u00f6nce uzunlu\u011fu 1 olan alt dizeler, sonra 2 olanlar, sonra 3 olanlar vb.<\/p>\nN<\/code> boyutunda bir dize i\u00e7in N x N<\/code> boyutunda dp<\/code> boolean matrisi olu\u015fturun.
\n2. longestPalindrome<\/code> ve maxLength<\/code> de\u011fi\u015fkenlerini ba\u015flat\u0131n (\u00f6rne\u011fin, ilk karakteri ba\u015flang\u0131\u00e7 palindromu olarak alabilirsiniz).
\n3. Uzunluk 1:<\/strong> T\u00fcm dp[i][i]<\/code> de\u011ferlerini true<\/code> olarak ayarlay\u0131n.
\n4. Uzunluk 2:<\/strong> i<\/code>‘den N-2<\/code>‘ye kadar d\u00f6ng\u00fc yap\u0131n. E\u011fer s.charAt(i) == s.charAt(i+1)<\/code> ise, dp[i][i+1] = true<\/code> olarak ayarlay\u0131n ve maxLength<\/code> ile longestPalindrome<\/code>‘\u0131 g\u00fcncelleyin.
\n5. Uzunluk 3’ten N’e kadar:<\/strong> len<\/code> (alt dize uzunlu\u011fu) 3’ten N<\/code>‘e kadar d\u00f6ng\u00fc yap\u0131n.
\n * Her len<\/code> i\u00e7in, i<\/code> (ba\u015flang\u0131\u00e7 indeksi) 0’dan N - len<\/code>‘e kadar d\u00f6ng\u00fc yap\u0131n.
\n * j<\/code> (biti\u015f indeksi) i + len - 1<\/code> olarak hesaplay\u0131n.
\n * E\u011fer s.charAt(i) == s.charAt(j)<\/code> ve dp[i+1][j-1]<\/code> true ise, dp[i][j] = true<\/code> olarak ayarlay\u0131n.
\n * E\u011fer dp[i][j]<\/code> true ise ve len<\/code> \u015fu anki maxLength<\/code>‘ten b\u00fcy\u00fckse, maxLength<\/code> ve longestPalindrome<\/code>‘\u0131 g\u00fcncelleyin.
\n6. Son olarak, longestPalindrome<\/code>‘\u0131 d\u00f6nd\u00fcr\u00fcn.<\/p>\nlen<\/code> (uzunluk), i<\/code> (ba\u015flang\u0131\u00e7 indeksi) ve j<\/code> (biti\u015f indeksi). Ancak j<\/code> i<\/code> ve len<\/code>‘e ba\u011fl\u0131d\u0131r. Temel olarak, $N^2$ h\u00fccreyi doldururuz ve her h\u00fccreyi doldurmak sabit zaman al\u0131r.
\n* Zaman karma\u015f\u0131kl\u0131\u011f\u0131 $O(N^2)$’dir.
\n* Alan karma\u015f\u0131kl\u0131\u011f\u0131 ise N x N<\/code> boyutundaki dp<\/code> matrisi i\u00e7in $O(N^2)$’dir.<\/p>\npublic class LongestPalindromicSubstring {\n\n \/\/ Dinamik Programlama Yakla\u015f\u0131m\u0131\n public String longestPalindromeDP(String s) {\n if (s == null || s.length() < 1) {\n return \"\";\n }\n\n int n = s.length();\n boolean[][] dp = new boolean[n][n]; \/\/ dp[i][j] true ise s[i...j] bir palindromdur\n\n String longestPalindrome = \"\";\n int maxLength = 0;\n\n \/\/ Tek karakterli alt dizeler her zaman palindromdur (uzunluk = 1)\n for (int i = 0; i < n; i++) {\n dp[i][i] = true;\n if (1 > maxLength) {\n maxLength = 1;\n longestPalindrome = s.substring(i, i + 1);\n }\n }\n\n \/\/ \u0130ki karakterli alt dizeler (uzunluk = 2)\n for (int i = 0; i < n - 1; i++) {\n if (s.charAt(i) == s.charAt(i + 1)) {\n dp[i][i + 1] = true;\n if (2 > maxLength) {\n maxLength = 2;\n longestPalindrome = s.substring(i, i + 2);\n }\n }\n }\n\n \/\/ Uzunluk 3'ten N'e kadar olan alt dizeler\n for (int len = 3; len <= n; len++) {\n for (int i = 0; i <= n - len; i++) {\n int j = i + len - 1; \/\/ Biti\u015f indeksi\n\n \/\/ s[i...j] bir palindrom mu?\n \/\/ s[i] == s[j] OLMALI VE s[i+1...j-1] B\u0130R PAL\u0130NDROM OLMALI\n if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {\n dp[i][j] = true;\n if (len > maxLength) {\n maxLength = len;\n longestPalindrome = s.substring(i, j + 1);\n }\n }\n }\n }\n return longestPalindrome;\n }\n\n \/\/ main metodu \u00f6rnek kullan\u0131m i\u00e7in\n public static void main(String[] args) {\n LongestPalindromicSubstring solver = new LongestPalindromicSubstring();\n\n System.out.println(\"Dynamic Programming:\");\n System.out.println(\"babad -> \" + solver.longestPalindromeDP(\"babad\")); \/\/ bab veya aba\n System.out.println(\"cbbd -> \" + solver.longestPalindromeDP(\"cbbd\")); \/\/ bb\n System.out.println(\"a -> \" + solver.longestPalindromeDP(\"a\")); \/\/ a\n System.out.println(\"ac -> \" + solver.longestPalindromeDP(\"ac\")); \/\/ a\n System.out.println(\"forgeeksskeegfor -> \" + solver.longestPalindromeDP(\"forgeeksskeegfor\")); \/\/ geeksskeeg\n }\n}<\/code><\/pre>\n
\n* “babad” -> “#b#a#b#a#d#” (uzunluk 5 -> 11)
\n* “cbbd” -> “#c#b#b#d#” (uzunluk 4 -> 9)<\/p>\nT<\/code> diyelim. T<\/code>‘nin uzunlu\u011fu 2*N + 1<\/code> olacakt\u0131r.
\n2. P<\/code> Dizisi:<\/strong> P[i]<\/code> ad\u0131nda bir dizi olu\u015fturun. P[i]<\/code>, T[i]<\/code> merkezli en uzun palindromun yar\u0131 uzunlu\u011funu (veya yar\u0131 \u00e7ap\u0131n\u0131) tutacakt\u0131r. \u00d6rne\u011fin, T[i]<\/code> merkezli palindrom T[i-P[i]...i+P[i]]<\/code> ise, P[i]<\/code> bu palindromun i<\/code>‘den ne kadar uzand\u0131\u011f\u0131n\u0131 g\u00f6sterir (kendi dahil).
\n3. C<\/code> (Center) ve R<\/code> (Right Boundary):<\/strong>
\n * C<\/code>: \u015eu ana kadar bulunan ve en sa\u011fa uzanan palindromun merkezi.
\n * R<\/code>: C<\/code> merkezli palindromun sa\u011f s\u0131n\u0131r\u0131 (C + P[C]<\/code>).<\/p>\nT<\/code> dizisi \u00fczerinde i<\/code> (0’dan T.length()-1<\/code>‘e kadar) ile d\u00f6ng\u00fc yap\u0131n.
\n Simetrik \u0130ndeks (i_mirror<\/code>):<\/strong> i_mirror = 2<\/em>C - i<\/code>. Bu, i<\/code>‘nin C<\/code>‘ye g\u00f6re simetrik indeksidir.
\n * Minimum Palindrom Yar\u0131\u00e7ap\u0131:<\/strong> i<\/code>‘deki palindromun en az min(P[i_mirror], R - i)<\/code> kadar olaca\u011f\u0131n\u0131 biliyoruz. E\u011fer i<\/code> R<\/code>‘nin i\u00e7indeyse, P[i]<\/code>‘nin ba\u015flang\u0131\u00e7 de\u011feri bu minimum de\u011ferdir. E\u011fer i<\/code> R<\/code>‘nin d\u0131\u015f\u0131ndaysa, P[i]<\/code> ba\u015flang\u0131\u00e7ta 0’d\u0131r.
\n * Geni\u015fletme:<\/strong> T[i - P[i] - 1] == T[i + P[i] + 1]<\/code> oldu\u011fu s\u00fcrece P[i]<\/code>‘yi art\u0131r\u0131n. (S\u0131n\u0131r kontrollerini unutmay\u0131n: i - P[i] - 1 >= 0<\/code> ve i + P[i] + 1 < T.length()<\/code>).
\n * C<\/code> ve R<\/code> G\u00fcncellemesi:<\/strong> E\u011fer i + P[i]<\/code> de\u011feri R<\/code>'den b\u00fcy\u00fckse (yani yeni bulunan palindrom daha sa\u011fa uzan\u0131yorsa), C<\/code>'yi i<\/code>'ye ve R<\/code>'yi i + P[i]<\/code>'ye g\u00fcncelleyin.<\/p>\nP<\/code> dizisindeki en b\u00fcy\u00fck de\u011feri (maxLen<\/code>) bulun. Bu maxLen<\/code>, d\u00f6n\u00fc\u015ft\u00fcr\u00fclm\u00fc\u015f dizedeki en uzun palindromun yar\u0131\u00e7ap\u0131d\u0131r.
\n * En uzun palindromun merkezi maxCenter<\/code> olacakt\u0131r.
\n * Orijinal dizedeki ba\u015flang\u0131\u00e7 indeksi (maxCenter - maxLen) \/ 2<\/code> olacakt\u0131r.
\n * Orijinal dizedeki uzunluk maxLen<\/code> olacakt\u0131r.<\/p>\ns.substring(start, start + maxLen)<\/code>.<\/p>\n
\n* Ana d\u00f6ng\u00fc $N'$ (d\u00f6n\u00fc\u015ft\u00fcr\u00fclm\u00fc\u015f dizenin uzunlu\u011fu, yakla\u015f\u0131k $2N$) kez \u00e7al\u0131\u015f\u0131r.
\n* P[i]<\/code>'nin her art\u0131r\u0131lmas\u0131 (geni\u015fletme ad\u0131m\u0131) toplamda N'<\/code> kez ger\u00e7ekle\u015fir. Bu, amortize edilmi\u015f analize g\u00f6re her karakterin sadece sabit say\u0131da kez ziyaret edildi\u011fi anlam\u0131na gelir.
\n* Zaman karma\u015f\u0131kl\u0131\u011f\u0131 $O(N)$'dir.
\n* Alan karma\u015f\u0131kl\u0131\u011f\u0131 P<\/code> dizisi ve d\u00f6n\u00fc\u015ft\u00fcr\u00fclm\u00fc\u015f dize i\u00e7in $O(N)$'dir.<\/p>\npublic class LongestPalindromicSubstring {\n\n \/\/ Manacher Algoritmas\u0131\n public String longestPalindromeManacher(String s) {\n if (s == null || s.length() == 0) {\n return \"\";\n }\n\n \/\/ 1. Dizeyi \u00d6n \u0130\u015fleme (Preprocessing)\n \/\/ Her karakter aras\u0131na ve ba\u015f\u0131na\/sonuna '#' ekleyerek\n \/\/ t\u00fcm palindromlar\u0131 tek uzunluklu hale getiriyoruz.\n StringBuilder t = new StringBuilder();\n t.append('$'); \/\/ Ba\u015flang\u0131\u00e7 i\u015fareti (s\u0131n\u0131r kontrol\u00fc i\u00e7in)\n t.append('#');\n for (char c : s.toCharArray()) {\n t.append(c);\n t.append('#');\n }\n t.append('@'); \/\/ Biti\u015f i\u015fareti (s\u0131n\u0131r kontrol\u00fc i\u00e7in)\n\n char[] T = t.toString().toCharArray(); \/\/ D\u00f6n\u00fc\u015ft\u00fcr\u00fclm\u00fc\u015f dize\n\n int n = T.length;\n int[] P = new int[n]; \/\/ P[i]: T[i] merkezli palindromun yar\u0131\u00e7ap\u0131\n int C = 0; \/\/ Center: En sa\u011fa uzanan palindromun merkezi\n int R = 0; \/\/ Right boundary: C merkezli palindromun sa\u011f s\u0131n\u0131r\u0131 (C + P[C])\n\n int maxLen = 0; \/\/ En uzun palindromun yar\u0131\u00e7ap\u0131\n int centerIndex = 0; \/\/ En uzun palindromun merkez indeksi\n\n for (int i = 1; i < n - 1; i++) { \/\/ '$' ve '@' i\u015faretlerini atl\u0131yoruz\n \/\/ i_mirror: i'nin C'ye g\u00f6re simetrik indeksi\n int i_mirror = 2 * C - i;\n\n \/\/ E\u011fer i, R'nin i\u00e7indeyse, P[i] en az min(P[i_mirror], R - i) olabilir\n \/\/ De\u011filse, P[i] ba\u015flang\u0131\u00e7ta 0'd\u0131r (tek karakterli palindrom)\n if (R > i) {\n P[i] = Math.min(R - i, P[i_mirror]);\n } else {\n P[i] = 0;\n }\n\n \/\/ Merkezden geni\u015fle\n \/\/ T[i - P[i] - 1] == T[i + P[i] + 1] oldu\u011fu s\u00fcrece P[i]'yi art\u0131r\n while (T[i + P[i] + 1] == T[i - P[i] - 1]) {\n P[i]++;\n }\n\n \/\/ E\u011fer yeni bulunan palindrom R'yi a\u015f\u0131yorsa, C ve R'yi g\u00fcncelle\n if (i + P[i] > R) {\n C = i;\n R = i + P[i];\n }\n\n \/\/ En uzun palindromu g\u00fcncelle\n if (P[i] > maxLen) {\n maxLen = P[i];\n centerIndex = i;\n }\n }\n\n \/\/ Orijinal dizedeki en uzun palindromu \u00e7\u0131kar\n \/\/ centerIndex: D\u00f6n\u00fc\u015ft\u00fcr\u00fclm\u00fc\u015f dizedeki merkezin indeksi\n \/\/ maxLen: D\u00f6n\u00fc\u015ft\u00fcr\u00fclm\u00fc\u015f dizedeki palindromun yar\u0131\u00e7ap\u0131\n \/\/ Orijinal dizedeki ba\u015flang\u0131\u00e7 indeksi: (centerIndex - maxLen) \/ 2\n \/\/ Orijinal dizedeki uzunluk: maxLen\n int startIndex = (centerIndex - maxLen) \/ 2;\n return s.substring(startIndex, startIndex + maxLen);\n }\n\n \/\/ main metodu \u00f6rnek kullan\u0131m i\u00e7in\n public static void main(String[] args) {\n LongestPalindromicSubstring solver = new LongestPalindromicSubstring();\n\n System.out.println(\"Manacher Algorithm:\");\n System.out.println(\"babad -> \" + solver.longestPalindromeManacher(\"babad\")); \/\/ bab\n System.out.println(\"cbbd -> \" + solver.longestPalindromeManacher(\"cbbd\")); \/\/ bb\n System.out.println(\"a -> \" + solver.longestPalindromeManacher(\"a\")); \/\/ a\n System.out.println(\"ac -> \" + solver.longestPalindromeManacher(\"ac\")); \/\/ a\n System.out.println(\"forgeeksskeegfor -> \" + solver.longestPalindromeManacher(\"forgeeksskeegfor\")); \/\/ geeksskeeg\n System.out.println(\"racecar -> \" + solver.longestPalindromeManacher(\"racecar\")); \/\/ racecar\n System.out.println(\"abba -> \" + solver.longestPalindromeManacher(\"abba\")); \/\/ abba\n }\n}<\/code><\/pre>\n
\n| :-------------------- | :----------------- | :---------------- | :----------------- | :---------------------------------------------------------------------- |
\n| Brute-Force<\/strong> | $O(N^3)$ | $O(N)$ | \u00c7ok Kolay | T\u00fcm alt dizeleri kontrol eder, en yava\u015f y\u00f6ntem. |
\n| Merkezden Geni\u015fletme<\/strong> | $O(N^2)$ | $O(1)$ | Orta | Her olas\u0131 merkezden d\u0131\u015far\u0131 do\u011fru geni\u015fler, pratikte iyi performans. |
\n| Dinamik Programlama<\/strong> | $O(N^2)$ | $O(N^2)$ | Orta | Alt problem \u00e7\u00f6z\u00fcmlerini depolayarak tekrar hesaplamalar\u0131 \u00f6nler. |
\n| Manacher Algoritmas\u0131<\/strong> | $O(N)$ | $O(N)$ | Zor | En verimli y\u00f6ntem, \u00f6zel \u00f6n i\u015fleme ve simetri kullan\u0131r. |<\/p>\nN<\/code> de\u011ferleri i\u00e7in veya bir kavram\u0131 h\u0131zl\u0131ca test etmek i\u00e7in kullan\u0131l\u0131r. Genellikle pratik uygulamalar i\u00e7in \u00f6nerilmez.
\n* Merkezden Geni\u015fletme:<\/strong> N^2<\/code> \u00e7\u00f6z\u00fcmlerin yeterli oldu\u011fu \u00e7o\u011fu pratik senaryo i\u00e7in iyi bir se\u00e7enektir. Uygulamas\u0131 nispeten kolayd\u0131r ve $O(1)$ alan karma\u015f\u0131kl\u0131\u011f\u0131 ile haf\u0131za dostudur.
\n* Dinamik Programlama:<\/strong> N^2<\/code> \u00e7\u00f6z\u00fcmlerin yeterli oldu\u011fu ve DP kavram\u0131n\u0131n anla\u015f\u0131lmas\u0131n\u0131n istendi\u011fi durumlarda kullan\u0131labilir. Ancak, $O(N^2)$ alan karma\u015f\u0131kl\u0131\u011f\u0131 nedeniyle haf\u0131za k\u0131s\u0131tlamalar\u0131 olan durumlarda dikkatli olunmal\u0131d\u0131r.
\n* Manacher Algoritmas\u0131:<\/strong>