पेलिंड्रोम क्या है?

पैलिंड्रोम एक शब्द, वाक्यांश, संख्या या वर्णों का अनुक्रम है जो आगे के समान ही पीछे की ओर पढ़ा जाता है। दूसरे शब्दों में, जब इसके वर्ण उलट दिए जाते हैं तो यह अपरिवर्तित रहता है।

उदाहरण

• "स्तर" एक पैलिन्ड्रोम है क्योंकि यह बाएँ से दाएँ और दाएँ से बाएँ समान पढ़ता है।

• "रेसकार" एक पैलिंड्रोम है।

• "12321" एक पैलिंड्रोम है।

• "मैडम" एक पैलिंड्रोम है।

सबसे लंबे पलिंड्रोमिक अनुवर्ती के लिए PHP प्रोग्राम

मान लीजिए X[0..n-1] लंबाई n का इनपुट अनुक्रम है और L(0, n-1) X[0..n-1] के सबसे लंबे पैलिंड्रोमिक अनुवर्ती की लंबाई है। यदि X का अंतिम और पहला अक्षर समान है, तो L(0, n-1) = L(1, n-2) 2. अन्यथा L(0, n-1) = MAX (L(1, n-1), L(0, n-2)).

डायनामिक प्रोग्रामिंग समाधान

 $y)? $x : $y; }

// Returns the length of the
// longest palindromic
// subsequence in seq
function lps($str)
{
$n = strlen($str);
$i; $j; $cl;

// Create a table to store
// results of subproblems
$L[][] = array(array());

// Strings of length 1 are
// palindrome of length 1
for ($i = 0; $i 

आउटपुट

The length of the longest palindromic subsequence is 7

दिए गए कोड का आउटपुट, जब इनपुट स्ट्रिंग "बीबीएबीसीबीसीएबी" के साथ निष्पादित किया जाता है, सबसे लंबे पैलिंड्रोमिक अनुवर्ती की लंबाई 7 है। इसका मतलब है कि इनपुट स्ट्रिंग "बीबीएबीसीबीसीएबी" के भीतर, लंबाई 7 का एक पैलिंड्रोमिक अनुवर्ती मौजूद है। मैं .ई. बबसीबीएबी। बीबीबीबीबी" और "बीबीसीबीबी" भी दिए गए अनुक्रम के पैलिंड्रोमिक अनुवर्ती हैं, लेकिन सबसे लंबे नहीं हैं। कोड गतिशील प्रोग्रामिंग का उपयोग करके इस लंबाई की सफलतापूर्वक गणना करता है और लौटाता है।

निष्कर्ष

निष्कर्ष में, प्रदान किया गया PHP कोड किसी दिए गए स्ट्रिंग में सबसे लंबे पैलिंड्रोमिक अनुवर्ती की लंबाई खोजने के लिए एक गतिशील प्रोग्रामिंग समाधान लागू करता है। जब इनपुट स्ट्रिंग "बीबीएबीसीबीसीएबी" के साथ निष्पादित किया जाता है, तो यह सही ढंग से निर्धारित करता है कि सबसे लंबे पैलिंड्रोमिक अनुवर्ती की लंबाई 7 (बीएबीसीबीएबी) है, हालांकि, कोड स्पष्ट रूप से अनुवर्ती प्रदान नहीं करता है। यह उन मामलों पर विचार करते हुए विभिन्न सबस्ट्रिंग के लिए लंबाई की एक तालिका बनाकर काम करता है जहां अक्षर मेल खाते हैं या मेल नहीं खाते हैं। एल्गोरिदम कुशलतापूर्वक नीचे से ऊपर दृष्टिकोण का उपयोग करके लंबाई की गणना करता है, जिसके परिणामस्वरूप वांछित आउटपुट प्राप्त होता है।