Skip to main content

Longest palindromic substring using dynamic programming

Here given code implementation process.

/*
    C program for
    Longest palindromic substring using dynamic programming
*/
#include <stdio.h>
#include <string.h>

void findLPS(char *text)
{
  // Get length of text
  int n = strlen(text);
  if (n == 0)
  {
    // When text is empty
    return;
  }
  int length = 1;
  int start = 0;
  int dp[n][n];
  for (int i = 0; i < n; ++i)
  {
    for (int j = 0; j < n; ++j)
    {
      dp[i][j] = 0;
    }
  }
  // Set diagonal elements value is 1
  for (int i = 0; i < n; ++i)
  {
    dp[i][i] = 1;
  }
  // Compare adjacent character
  for (int i = 0; i < n - 1; ++i)
  {
    if (text[i] == text[i + 1])
    {
      // When adjacent elements is similar
      dp[i][i + 1] = 1;
      // Change resultant length
      length = 2;
      start = i;
    }
  }
  for (int k = 3; k <= n; ++k)
  {
    for (int i = 0; i < n - k + 1; ++i)
    {
      int j = i + k - 1;
      if (dp[i + 1][j - 1] && text[i] == text[j])
      {
        dp[i][j] = 1;
        if (k > length)
        {
          // Change resultant length
          length = k;
          // Update resultant starting location
          start = i;
        }
      }
    }
  }
  // Display given text
  printf("\n Given string : %s", text);
  printf("\n Result : ");
  // Display resultant palindrome
  for (int i = start; i <= start + length - 1; ++i)
  {
    printf("%c", text[i]);
  }
  // Display length of resultant palindrome
  printf("\n Resultant length : %d", length);
}
int main(int argc, char
  const *argv[])
{
  // Test
  // iiii => 4
  findLPS("nitiiiigi");
  // ivfvi => 5
  findLPS("vvvvivfvim");
  // civic => 5
  findLPS("xyzacivicxrs");
  // opo => 3
  findLPS("ttoopo");
  return 0;
}

Output

 Given string : nitiiiigi
 Result : iiii
 Resultant length : 4
 Given string : vvvvivfvim
 Result : ivfvi
 Resultant length : 5
 Given string : xyzacivicxrs
 Result : civic
 Resultant length : 5
 Given string : ttoopo
 Result : opo
 Resultant length : 3
// Java program for
// Longest palindromic substring using dynamic programming
public class LongestPalindrome
{
    public void findLPS(String text)
    {
        // Get length of text
        int n = text.length();
        if (n == 0)
        {
            // When text is empty
            return;
        }
        int length = 1;
        int start = 0;
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                dp[i][j] = 0;
            }
        }
        // Set diagonal elements value is 1
        for (int i = 0; i < n; ++i)
        {
            dp[i][i] = 1;
        }
        // Compare adjacent character
        for (int i = 0; i < n - 1; ++i)
        {
            if (text.charAt(i) == text.charAt(i + 1))
            {
                // When adjacent elements is similar
                dp[i][i + 1] = 1;
                // Change resultant length
                length = 2;
                start = i;
            }
        }
        for (int k = 3; k <= n; ++k)
        {
            for (int i = 0; i < n - k + 1; ++i)
            {
                int j = i + k - 1;
                if (dp[i + 1][j - 1] != 0 && text.charAt(i) == text.charAt(j))
                {
                    dp[i][j] = 1;
                    if (k > length)
                    {
                        // Change resultant length
                        length = k;
                        // Update resultant starting location
                        start = i;
                    }
                }
            }
        }
        // Display given text
        System.out.print("\n Given string : " + text);
        System.out.print("\n Result : ");
        // Display resultant palindrome
        for (int i = start; i <= start + length - 1; ++i)
        {
            System.out.print(text.charAt(i));
        }
        // Display length of resultant palindrome
        System.out.print("\n Resultant length : " + length);
    }
    public static void main(String[] args)
    {
        LongestPalindrome task = new LongestPalindrome();
        // Test
        // iiii => 4
        task.findLPS("nitiiiigi");
        // ivfvi => 5
        task.findLPS("vvvvivfvim");
        // civic => 5
        task.findLPS("xyzacivicxrs");
        // opo => 3
        task.findLPS("ttoopo");
    }
}

Output

 Given string : nitiiiigi
 Result : iiii
 Resultant length : 4
 Given string : vvvvivfvim
 Result : ivfvi
 Resultant length : 5
 Given string : xyzacivicxrs
 Result : civic
 Resultant length : 5
 Given string : ttoopo
 Result : opo
 Resultant length : 3
// Include header file
#include <iostream>
#include <string>
using namespace std;

// C++ program for
// Longest palindromic substring using dynamic programming

class LongestPalindrome
{
  public: void findLPS(string text)
  {
    // Get length of text
    int n = text.length();
    if (n == 0)
    {
      // When text is empty
      return;
    }
    int length = 1;
    int start = 0;
    int dp[n][n];
    for (int i = 0; i < n; ++i)
    {
      for (int j = 0; j < n; ++j)
      {
        dp[i][j] = 0;
      }
    }
    // Set diagonal elements value is 1
    for (int i = 0; i < n; ++i)
    {
      dp[i][i] = 1;
    }
    // Compare adjacent character
    for (int i = 0; i < n - 1; ++i)
    {
      if (text[i] == text[i + 1])
      {
        // When adjacent elements is similar
        dp[i][i + 1] = 1;
        // Change resultant length
        length = 2;
        start = i;
      }
    }
    for (int k = 3; k <= n; ++k)
    {
      for (int i = 0; i < n - k + 1; ++i)
      {
        int j = i + k - 1;
        if (dp[i + 1][j - 1] != 0 && text[i] == text[j])
        {
          dp[i][j] = 1;
          if (k > length)
          {
            // Change resultant length
            length = k;
            // Update resultant starting location
            start = i;
          }
        }
      }
    }
    // Display given text
    cout << "\n Given string : " << text;
    cout << "\n Result : ";
    // Display resultant palindrome
    for (int i = start; i <= start + length - 1; ++i)
    {
      cout << text[i];
    }
    // Display length of resultant palindrome
    cout << "\n Resultant length : " << length;
  }
};
int main()
{
  LongestPalindrome *task = new LongestPalindrome();
  // Test
  // iiii => 4
  task->findLPS("nitiiiigi");
  // ivfvi => 5
  task->findLPS("vvvvivfvim");
  // civic => 5
  task->findLPS("xyzacivicxrs");
  // opo => 3
  task->findLPS("ttoopo");
  return 0;
}

Output

 Given string : nitiiiigi
 Result : iiii
 Resultant length : 4
 Given string : vvvvivfvim
 Result : ivfvi
 Resultant length : 5
 Given string : xyzacivicxrs
 Result : civic
 Resultant length : 5
 Given string : ttoopo
 Result : opo
 Resultant length : 3
// Include namespace system
using System;
// Csharp program for
// Longest palindromic substring using dynamic programming
public class LongestPalindrome
{
  public void findLPS(String text)
  {
    // Get length of text
    int n = text.Length;
    if (n == 0)
    {
      // When text is empty
      return;
    }
    int length = 1;
    int start = 0;
    int[,] dp = new int[n,n];
    for (int i = 0; i < n; ++i)
    {
      for (int j = 0; j < n; ++j)
      {
        dp[i,j] = 0;
      }
    }
    // Set diagonal elements value is 1
    for (int i = 0; i < n; ++i)
    {
      dp[i,i] = 1;
    }
    // Compare adjacent character
    for (int i = 0; i < n - 1; ++i)
    {
      if (text[i] == text[i + 1])
      {
        // When adjacent elements is similar
        dp[i,i + 1] = 1;
        // Change resultant length
        length = 2;
        start = i;
      }
    }
    for (int k = 3; k <= n; ++k)
    {
      for (int i = 0; i < n - k + 1; ++i)
      {
        int j = i + k - 1;
        if (dp[i + 1,j - 1] != 0 && text[i] == text[j])
        {
          dp[i,j] = 1;
          if (k > length)
          {
            // Change resultant length
            length = k;
            // Update resultant starting location
            start = i;
          }
        }
      }
    }
    // Display given text
    Console.Write("\n Given string : " + text);
    Console.Write("\n Result : ");
    // Display resultant palindrome
    for (int i = start; i <= start + length - 1; ++i)
    {
      Console.Write(text[i]);
    }
    // Display length of resultant palindrome
    Console.Write("\n Resultant length : " + length);
  }
  public static void Main(String[] args)
  {
    LongestPalindrome task = new LongestPalindrome();
    // Test
    // iiii => 4
    task.findLPS("nitiiiigi");
    // ivfvi => 5
    task.findLPS("vvvvivfvim");
    // civic => 5
    task.findLPS("xyzacivicxrs");
    // opo => 3
    task.findLPS("ttoopo");
  }
}

Output

 Given string : nitiiiigi
 Result : iiii
 Resultant length : 4
 Given string : vvvvivfvim
 Result : ivfvi
 Resultant length : 5
 Given string : xyzacivicxrs
 Result : civic
 Resultant length : 5
 Given string : ttoopo
 Result : opo
 Resultant length : 3
package main
import "fmt"
// Go program for
// Longest palindromic substring using dynamic programming

func findLPS(text string) {
  // Get length of text
  var n int = len(text)
  if n == 0 {
    // When text is empty
    return
  }
  var length int = 1
  var start int = 0
  var dp = make([][] int, n)
  for i := 0; i < n; i++ {
    dp[i] = make([]int,n)
  }
  // Set diagonal elements value is 1
  for i := 0 ; i < n ; i++ {
    dp[i][i] = 1
  }
  // Compare adjacent character
  for i := 0 ; i < n - 1 ; i++ {
    if text[i] == text[i + 1] {
      // When adjacent elements is similar
      dp[i][i + 1] = 1
      // Change resultant length
      length = 2
      start = i
    }
  }
  for k := 3 ; k <= n ; k++ {
    for i := 0 ; i < n - k + 1 ; i++ {
      var j int = i + k - 1
      if dp[i + 1][j - 1] != 0 && text[i] == text[j] {
        dp[i][j] = 1
        if k > length {
          // Change resultant length
          length = k
          // Update resultant starting location
          start = i
        }
      }
    }
  }
  // Display given text
  fmt.Print("\n Given string : ", text)
  fmt.Print("\n Result : ")
  // Display resultant palindrome
  for i := start ; i <= start + length - 1 ; i++ {
    fmt.Print(string(text[i]))
  }
  // Display length of resultant palindrome
  fmt.Print("\n Resultant length : ", length)
}
func main() {
  
  // Test
  // iiii => 4
  findLPS("nitiiiigi")
  // ivfvi => 5
  findLPS("vvvvivfvim")
  // civic => 5
  findLPS("xyzacivicxrs")
  // opo => 3
  findLPS("ttoopo")
}

Output

 Given string : nitiiiigi
 Result : iiii
 Resultant length : 4
 Given string : vvvvivfvim
 Result : ivfvi
 Resultant length : 5
 Given string : xyzacivicxrs
 Result : civic
 Resultant length : 5
 Given string : ttoopo
 Result : opo
 Resultant length : 3
<?php
// Php program for
// Longest palindromic substring using dynamic programming
class LongestPalindrome
{
  public  function findLPS($text)
  {
    // Get length of text
    $n = strlen($text);
    if ($n == 0)
    {
      // When text is empty
      return;
    }
    $length = 1;
    $start = 0;
    $dp = array_fill(0, $n, array_fill(0, $n, 0));
    // Set diagonal elements value is 1
    for ($i = 0; $i < $n; ++$i)
    {
      $dp[$i][$i] = 1;
    }
    // Compare adjacent character
    for ($i = 0; $i < $n - 1; ++$i)
    {
      if ($text[$i] == $text[$i + 1])
      {
        // When adjacent elements is similar
        $dp[$i][$i + 1] = 1;
        // Change resultant length
        $length = 2;
        $start = $i;
      }
    }
    for ($k = 3; $k <= $n; ++$k)
    {
      for ($i = 0; $i < $n - $k + 1; ++$i)
      {
        $j = $i + $k - 1;
        if ($dp[$i + 1][$j - 1] != 0 && $text[$i] == $text[$j])
        {
          $dp[$i][$j] = 1;
          if ($k > $length)
          {
            // Change resultant length
            $length = $k;
            // Update resultant starting location
            $start = $i;
          }
        }
      }
    }
    // Display given text
    echo("\n Given string : ".$text);
    echo("\n Result : ");
    // Display resultant palindrome
    for ($i = $start; $i <= $start + $length - 1; ++$i)
    {
      echo($text[$i]);
    }
    // Display length of resultant palindrome
    echo("\n Resultant length : ".$length);
  }
}

function main()
{
  $task = new LongestPalindrome();
  // Test
  // iiii => 4
  $task->findLPS("nitiiiigi");
  // ivfvi => 5
  $task->findLPS("vvvvivfvim");
  // civic => 5
  $task->findLPS("xyzacivicxrs");
  // opo => 3
  $task->findLPS("ttoopo");
}
main();

Output

 Given string : nitiiiigi
 Result : iiii
 Resultant length : 4
 Given string : vvvvivfvim
 Result : ivfvi
 Resultant length : 5
 Given string : xyzacivicxrs
 Result : civic
 Resultant length : 5
 Given string : ttoopo
 Result : opo
 Resultant length : 3
// Node JS program for
// Longest palindromic substring using dynamic programming
class LongestPalindrome
{
  findLPS(text)
  {
    // Get length of text
    var n = text.length;
    if (n == 0)
    {
      // When text is empty
      return;
    }
    var length = 1;
    var start = 0;
    var dp = Array(n).fill(0).map(() => new Array(n).fill(0));
    // Set diagonal elements value is 1
    for (var i = 0; i < n; ++i)
    {
      dp[i][i] = 1;
    }
    // Compare adjacent character
    for (var i = 0; i < n - 1; ++i)
    {
      if (text.charAt(i) == text.charAt(i + 1))
      {
        // When adjacent elements is similar
        dp[i][i + 1] = 1;
        // Change resultant length
        length = 2;
        start = i;
      }
    }
    for (var k = 3; k <= n; ++k)
    {
      for (var i = 0; i < n - k + 1; ++i)
      {
        var j = i + k - 1;
        if (dp[i + 1][j - 1] != 0 && 
                    text.charAt(i) == text.charAt(j))
        {
          dp[i][j] = 1;
          if (k > length)
          {
            // Change resultant length
            length = k;
            // Update resultant starting location
            start = i;
          }
        }
      }
    }
    // Display given text
    process.stdout.write("\n Given string : " + text);
    process.stdout.write("\n Result : ");
    // Display resultant palindrome
    for (var i = start; i <= start + length - 1; ++i)
    {
      process.stdout.write(text.charAt(i));
    }
    // Display length of resultant palindrome
    process.stdout.write("\n Resultant length : " + length);
  }
}

function main()
{
  var task = new LongestPalindrome();
  // Test
  // iiii => 4
  task.findLPS("nitiiiigi");
  // ivfvi => 5
  task.findLPS("vvvvivfvim");
  // civic => 5
  task.findLPS("xyzacivicxrs");
  // opo => 3
  task.findLPS("ttoopo");
}
main();

Output

 Given string : nitiiiigi
 Result : iiii
 Resultant length : 4
 Given string : vvvvivfvim
 Result : ivfvi
 Resultant length : 5
 Given string : xyzacivicxrs
 Result : civic
 Resultant length : 5
 Given string : ttoopo
 Result : opo
 Resultant length : 3
#  Python 3 program for
#  Longest palindromic substring using dynamic programming
class LongestPalindrome :
  def findLPS(self, text) :
    #  Get length of text
    n = len(text)
    if (n == 0) :
      #  When text is empty
      return
    
    length = 1
    start = 0
    dp = [[0] * (n) for _ in range(n) ]
    i = 0
    #  Set diagonal elements value is 1
    while (i < n) :
      dp[i][i] = 1
      i += 1
    
    i = 0
    #  Compare adjacent character
    while (i < n - 1) :
      if (text[i] == text[i + 1]) :
        #  When adjacent elements is similar
        dp[i][i + 1] = 1
        #  Change resultant length
        length = 2
        start = i
      
      i += 1
    
    k = 3
    while (k <= n) :
      i = 0
      while (i < n - k + 1) :
        j = i + k - 1
        if (dp[i + 1][j - 1] != 0 and text[i] == text[j]) :
          dp[i][j] = 1
          if (k > length) :
            #  Change resultant length
            length = k
            #  Update resultant starting location
            start = i
          
        
        i += 1
      
      k += 1
    
    #  Display given text
    print("\n Given string : ", text, end = "")
    print("\n Result : ", end = "")
    i = start
    #  Display resultant palindrome
    while (i <= start + length - 1) :
      print(text[i], end = "")
      i += 1
    
    #  Display length of resultant palindrome
    print("\n Resultant length : ", length, end = "")
  

def main() :
  task = LongestPalindrome()
  #  Test
  #  iiii => 4
  task.findLPS("nitiiiigi")
  #  ivfvi => 5
  task.findLPS("vvvvivfvim")
  #  civic => 5
  task.findLPS("xyzacivicxrs")
  #  opo => 3
  task.findLPS("ttoopo")

if __name__ == "__main__": main()

Output

 Given string :  nitiiiigi
 Result : iiii
 Resultant length :  4
 Given string :  vvvvivfvim
 Result : ivfvi
 Resultant length :  5
 Given string :  xyzacivicxrs
 Result : civic
 Resultant length :  5
 Given string :  ttoopo
 Result : opo
 Resultant length :  3
#  Ruby program for
#  Longest palindromic substring using dynamic programming
class LongestPalindrome 
  def findLPS(text) 
    #  Get length of text
    n = text.length
    if (n == 0) 
      #  When text is empty
      return
    end

    length = 1
    start = 0
    dp = Array.new(n) {Array.new(n) {0}}
    i = 0
    #  Set diagonal elements value is 1
    while (i < n) 
      dp[i][i] = 1
      i += 1
    end

    i = 0
    #  Compare adjacent character
    while (i < n - 1) 
      if (text[i] == text[i + 1]) 
        #  When adjacent elements is similar
        dp[i][i + 1] = 1
        #  Change resultant length
        length = 2
        start = i
      end

      i += 1
    end

    k = 3
    while (k <= n) 
      i = 0
      while (i < n - k + 1) 
        j = i + k - 1
        if (dp[i + 1][j - 1] != 0 && text[i] == text[j]) 
          dp[i][j] = 1
          if (k > length) 
            #  Change resultant length
            length = k
            #  Update resultant starting location
            start = i
          end

        end

        i += 1
      end

      k += 1
    end

    #  Display given text
    print("\n Given string : ", text)
    print("\n Result : ")
    i = start
    #  Display resultant palindrome
    while (i <= start + length - 1) 
      print(text[i])
      i += 1
    end

    #  Display length of resultant palindrome
    print("\n Resultant length : ", length)
  end

end

def main() 
  task = LongestPalindrome.new()
  #  Test
  #  iiii => 4
  task.findLPS("nitiiiigi")
  #  ivfvi => 5
  task.findLPS("vvvvivfvim")
  #  civic => 5
  task.findLPS("xyzacivicxrs")
  #  opo => 3
  task.findLPS("ttoopo")
end

main()

Output

 Given string : nitiiiigi
 Result : iiii
 Resultant length : 4
 Given string : vvvvivfvim
 Result : ivfvi
 Resultant length : 5
 Given string : xyzacivicxrs
 Result : civic
 Resultant length : 5
 Given string : ttoopo
 Result : opo
 Resultant length : 3
// Scala program for
// Longest palindromic substring using dynamic programming
class LongestPalindrome()
{
  def findLPS(text: String): Unit = {
    // Get length of text
    var n: Int = text.length();
    if (n == 0)
    {
      // When text is empty
      return;
    }
    var length: Int = 1;
    var start: Int = 0;
    var dp: Array[Array[Int]] = Array.fill[Int](n, n)(0);
    var i: Int = 0;
    // Set diagonal elements value is 1
    while (i < n)
    {
      dp(i)(i) = 1;
      i += 1;
    }
    i = 0;
    // Compare adjacent character
    while (i < n - 1)
    {
      if (text.charAt(i) == text.charAt(i + 1))
      {
        // When adjacent elements is similar
        dp(i)(i + 1) = 1;
        // Change resultant length
        length = 2;
        start = i;
      }
      i += 1;
    }
    var k: Int = 3;
    while (k <= n)
    {
      i = 0;
      while (i < n - k + 1)
      {
        var j: Int = i + k - 1;
        if (dp(i + 1)(j - 1) != 0 && 
                    text.charAt(i) == text.charAt(j))
        {
          dp(i)(j) = 1;
          if (k > length)
          {
            // Change resultant length
            length = k;
            // Update resultant starting location
            start = i;
          }
        }
        i += 1;
      }
      k += 1;
    }
    // Display given text
    print("\n Given string : " + text);
    print("\n Result : ");
    i = start;
    // Display resultant palindrome
    while (i <= start + length - 1)
    {
      print(text.charAt(i));
      i += 1;
    }
    // Display length of resultant palindrome
    print("\n Resultant length : " + length);
  }
}
object Main
{
  def main(args: Array[String]): Unit = {
    var task: LongestPalindrome = new LongestPalindrome();
    // Test
    // iiii => 4
    task.findLPS("nitiiiigi");
    // ivfvi => 5
    task.findLPS("vvvvivfvim");
    // civic => 5
    task.findLPS("xyzacivicxrs");
    // opo => 3
    task.findLPS("ttoopo");
  }
}

Output

 Given string : nitiiiigi
 Result : iiii
 Resultant length : 4
 Given string : vvvvivfvim
 Result : ivfvi
 Resultant length : 5
 Given string : xyzacivicxrs
 Result : civic
 Resultant length : 5
 Given string : ttoopo
 Result : opo
 Resultant length : 3
import Foundation;
// Swift 4 program for
// Longest palindromic substring using dynamic programming
class LongestPalindrome
{
  func findLPS(_ data: String)
  {
        let text = Array(data);
    // Get length of text
    let n: Int = text.count;
    if (n == 0)
    {
      // When text is empty
      return;
    }
    var length: Int = 1;
    var start: Int = 0;
    var dp: [[Int]] = 
          Array(repeating: Array(repeating: 0, count: n), count: n);
    var i: Int = 0;
    // Set diagonal elements value is 1
    while (i < n)
    {
      dp[i][i] = 1;
      i += 1;
    }
    i = 0;
    // Compare adjacent character
    while (i < n - 1)
    {
      if (text[i] == text[i + 1])
      {
        // When adjacent elements is similar
        dp[i][i + 1] = 1;
        // Change resultant length
        length = 2;
        start = i;
      }
      i += 1;
    }
    var k: Int = 3;
    while (k <= n)
    {
      i = 0;
      while (i < n - k + 1)
      {
        let j: Int = i + k - 1;
        if (dp[i + 1][j - 1]  != 0 && text[i] == text[j])
        {
          dp[i][j] = 1;
          if (k > length)
          {
            // Change resultant length
            length = k;
            // Update resultant starting location
            start = i;
          }
        }
        i += 1;
      }
      k += 1;
    }
    // Display given text
    print("\n Given string : ", data, terminator: "");
    print("\n Result : ", terminator: "");
    i = start;
    // Display resultant palindrome
    while (i <= start + length - 1)
    {
      print(text[i], terminator: "");
      i += 1;
    }
    // Display length of resultant palindrome
    print("\n Resultant length : ", length, terminator: "");
  }
}
func main()
{
  let task: LongestPalindrome = LongestPalindrome();
  // Test
  // iiii => 4
  task.findLPS("nitiiiigi");
  // ivfvi => 5
  task.findLPS("vvvvivfvim");
  // civic => 5
  task.findLPS("xyzacivicxrs");
  // opo => 3
  task.findLPS("ttoopo");
}
main();

Output

 Given string :  nitiiiigi
 Result : iiii
 Resultant length :  4
 Given string :  vvvvivfvim
 Result : ivfvi
 Resultant length :  5
 Given string :  xyzacivicxrs
 Result : civic
 Resultant length :  5
 Given string :  ttoopo
 Result : opo
 Resultant length :  3
// Kotlin program for
// Longest palindromic substring using dynamic programming
class LongestPalindrome
{
  fun findLPS(text: String): Unit
  {
    // Get length of text
    val n: Int = text.length;
    if (n == 0)
    {
      // When text is empty
      return;
    }
    var length: Int = 1;
    var start: Int = 0;
    val dp: Array < Array < Int >> = Array(n)
    {
      Array(n)
      {
        0
      }
    };
    var i: Int = 0;
    // Set diagonal elements value is 1
    while (i < n)
    {
      dp[i][i] = 1;
      i += 1;
    }
    i = 0;
    // Compare adjacent character
    while (i < n - 1)
    {
      if (text.get(i) == text.get(i + 1))
      {
        // When adjacent elements is similar
        dp[i][i + 1] = 1;
        // Change resultant length
        length = 2;
        start = i;
      }
      i += 1;
    }
    var k: Int = 3;
    while (k <= n)
    {
      i = 0;
      while (i < n - k + 1)
      {
        val j: Int = i + k - 1;
        if (dp[i + 1][j - 1] != 0 && text.get(i) == text.get(j))
        {
          dp[i][j] = 1;
          if (k > length)
          {
            // Change resultant length
            length = k;
            // Update resultant starting location
            start = i;
          }
        }
        i += 1;
      }
      k += 1;
    }
    // Display given text
    print("\n Given string : " + text);
    print("\n Result : ");
    i = start;
    // Display resultant palindrome
    while (i <= start + length - 1)
    {
      print(text.get(i));
      i += 1;
    }
    // Display length of resultant palindrome
    print("\n Resultant length : " + length);
  }
}
fun main(args: Array < String > ): Unit
{
  val task: LongestPalindrome = LongestPalindrome();
  // Test
  // iiii => 4
  task.findLPS("nitiiiigi");
  // ivfvi => 5
  task.findLPS("vvvvivfvim");
  // civic => 5
  task.findLPS("xyzacivicxrs");
  // opo => 3
  task.findLPS("ttoopo");
}

Output

 Given string : nitiiiigi
 Result : iiii
 Resultant length : 4
 Given string : vvvvivfvim
 Result : ivfvi
 Resultant length : 5
 Given string : xyzacivicxrs
 Result : civic
 Resultant length : 5
 Given string : ttoopo
 Result : opo
 Resultant length : 3
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment