Longest palindromic substring recursive
Here given code implementation process.
/*
C program for
Longest palindromic substring recursive
*/
#include <stdio.h>
#include <string.h>
int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
int maxLength(char *text, int s, int e, int length)
{
if (s == e)
{
return length + 1;
}
if (s > e)
{
return length;
}
if (text[s] == text[e])
{
// When boundary element are similar.
// Find the palindrome length in possible three cases.
// Inner substring, start+1 to end and start to end-1
return maxValue(
maxLength(text, s + 1, e - 1, length + 2),
maxValue(maxLength(text, s + 1, e, 0),
maxLength(text, s, e - 1, 0)));
}
return maxValue(maxLength(text, s + 1, e, 0),
maxLength(text, s, e - 1, 0));
}
void lengthOfLPS(char *text)
{
// Get length of text
int n = strlen(text);
if (n == 0)
{
// When text is empty
return;
}
// Display given text
printf("\n Given string : %s", text);
// 1st parameters are passing text
// 2nd parameter is start point
// 3rd parameter is last point
// 4th is resultant length
int length = maxLength(text, 0, n - 1, 0);
// Display length of resultant palindrome
printf("\n Resultant palindrome length : %d", length);
}
int main(int argc, char
const *argv[])
{
// Test
// iiii => 4
lengthOfLPS("nitiiiigi");
// ivfvi => 5
lengthOfLPS("vvvvivfvim");
// civic => 5
lengthOfLPS("xyzacivicxrs");
// opo => 3
lengthOfLPS("ttoopo");
return 0;
}
Output
Given string : nitiiiigi
Resultant palindrome length : 4
Given string : vvvvivfvim
Resultant palindrome length : 5
Given string : xyzacivicxrs
Resultant palindrome length : 5
Given string : ttoopo
Resultant palindrome length : 3
// Java program for
// Longest palindromic substring recursive
public class LongestPalindrome
{
public int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
public int maxPalindromicLength(String text, int s, int e, int length)
{
if (s == e)
{
return length + 1;
}
if (s > e)
{
return length;
}
if (text.charAt(s) == text.charAt(e))
{
// When boundary element are similar.
// Find the palindrome length in possible three cases.
// Inner substring, start+1 to end and start to end-1
return maxValue(maxPalindromicLength(text, s + 1, e - 1, length + 2),
maxValue(maxPalindromicLength(text, s + 1, e, 0),
maxPalindromicLength(text, s, e - 1, 0)));
}
return maxValue(maxPalindromicLength(text, s + 1, e, 0),
maxPalindromicLength(text, s, e - 1, 0));
}
public void lengthOfLPS(String text)
{
// Get length of text
int n = text.length();
if (n == 0)
{
// When text is empty
return;
}
// Display given text
System.out.print("\n Given string : " + text );
// 1st parameters are passing text
// 2nd parameter is start point
// 3rd parameter is last point
// 4th is resultant length
int length = maxPalindromicLength(text, 0, n - 1, 0);
// Display length of resultant palindrome
System.out.print("\n Resultant palindrome length : " + length );
}
public static void main(String[] args)
{
LongestPalindrome task = new LongestPalindrome();
// Test
// iiii => 4
task.lengthOfLPS("nitiiiigi");
// ivfvi => 5
task.lengthOfLPS("vvvvivfvim");
// civic => 5
task.lengthOfLPS("xyzacivicxrs");
// opo => 3
task.lengthOfLPS("ttoopo");
}
}
Output
Given string : nitiiiigi
Resultant palindrome length : 4
Given string : vvvvivfvim
Resultant palindrome length : 5
Given string : xyzacivicxrs
Resultant palindrome length : 5
Given string : ttoopo
Resultant palindrome length : 3
// Include header file
#include <iostream>
#include <string>
using namespace std;
// C++ program for
// Longest palindromic substring recursive
class LongestPalindrome
{
public: int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
int maxPalindromicLength(string text, int s, int e, int length)
{
if (s == e)
{
return length + 1;
}
if (s > e)
{
return length;
}
if (text[s] == text[e])
{
// When boundary element are similar.
// Find the palindrome length in possible three cases.
// Inner substring, start+1 to end and start to end-1
return this->maxValue(
this->maxPalindromicLength(text, s + 1, e - 1, length + 2),
this->maxValue(this->maxPalindromicLength(text, s + 1, e, 0),
this->maxPalindromicLength(text, s, e - 1, 0)));
}
return this->maxValue(this->maxPalindromicLength(text, s + 1, e, 0),
this->maxPalindromicLength(text, s, e - 1, 0));
}
void lengthOfLPS(string text)
{
// Get length of text
int n = text.length();
if (n == 0)
{
// When text is empty
return;
}
// Display given text
cout << "\n Given string : " << text;
// 1st parameters are passing text
// 2nd parameter is start point
// 3rd parameter is last point
// 4th is resultant length
int length = this->maxPalindromicLength(text, 0, n - 1, 0);
// Display length of resultant palindrome
cout << "\n Resultant palindrome length : " << length;
}
};
int main()
{
LongestPalindrome *task = new LongestPalindrome();
// Test
// iiii => 4
task->lengthOfLPS("nitiiiigi");
// ivfvi => 5
task->lengthOfLPS("vvvvivfvim");
// civic => 5
task->lengthOfLPS("xyzacivicxrs");
// opo => 3
task->lengthOfLPS("ttoopo");
return 0;
}
Output
Given string : nitiiiigi
Resultant palindrome length : 4
Given string : vvvvivfvim
Resultant palindrome length : 5
Given string : xyzacivicxrs
Resultant palindrome length : 5
Given string : ttoopo
Resultant palindrome length : 3
// Include namespace system
using System;
// Csharp program for
// Longest palindromic substring recursive
public class LongestPalindrome
{
public int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
public int maxPalindromicLength(String text, int s, int e, int length)
{
if (s == e)
{
return length + 1;
}
if (s > e)
{
return length;
}
if (text[s] == text[e])
{
// When boundary element are similar.
// Find the palindrome length in possible three cases.
// Inner substring, start+1 to end and start to end-1
return this.maxValue(
this.maxPalindromicLength(text, s + 1, e - 1, length + 2),
this.maxValue(this.maxPalindromicLength(text, s + 1, e, 0),
this.maxPalindromicLength(text, s, e - 1, 0)));
}
return this.maxValue(this.maxPalindromicLength(text, s + 1, e, 0),
this.maxPalindromicLength(text, s, e - 1, 0));
}
public void lengthOfLPS(String text)
{
// Get length of text
int n = text.Length;
if (n == 0)
{
// When text is empty
return;
}
// Display given text
Console.Write("\n Given string : " + text);
// 1st parameters are passing text
// 2nd parameter is start point
// 3rd parameter is last point
// 4th is resultant length
int length = this.maxPalindromicLength(text, 0, n - 1, 0);
// Display length of resultant palindrome
Console.Write("\n Resultant palindrome length : " + length);
}
public static void Main(String[] args)
{
LongestPalindrome task = new LongestPalindrome();
// Test
// iiii => 4
task.lengthOfLPS("nitiiiigi");
// ivfvi => 5
task.lengthOfLPS("vvvvivfvim");
// civic => 5
task.lengthOfLPS("xyzacivicxrs");
// opo => 3
task.lengthOfLPS("ttoopo");
}
}
Output
Given string : nitiiiigi
Resultant palindrome length : 4
Given string : vvvvivfvim
Resultant palindrome length : 5
Given string : xyzacivicxrs
Resultant palindrome length : 5
Given string : ttoopo
Resultant palindrome length : 3
package main
import "fmt"
// Go program for
// Longest palindromic substring recursive
func maxValue(a, b int) int {
if a > b {
return a
}
return b
}
func maxPalindromicLength(text string, s int, e int, length int) int {
if s == e {
return length + 1
}
if s > e {
return length
}
if text[s] == text[e] {
// When boundary element are similar.
// Find the palindrome length in possible three cases.
// Inner substring, start+1 to end and start to end-1
return maxValue(maxPalindromicLength(text, s + 1, e - 1, length + 2),
maxValue(maxPalindromicLength(text, s + 1, e, 0),
maxPalindromicLength(text, s, e - 1, 0)))
}
return maxValue(maxPalindromicLength(text, s + 1, e, 0),
maxPalindromicLength(text, s, e - 1, 0))
}
func lengthOfLPS(text string) {
// Get length of text
var n int = len(text)
if n == 0 {
// When text is empty
return
}
// Display given text
fmt.Print("\n Given string : ", text)
// 1st parameters are passing text
// 2nd parameter is start point
// 3rd parameter is last point
// 4th is resultant length
var length int = maxPalindromicLength(text, 0, n - 1, 0)
// Display length of resultant palindrome
fmt.Print("\n Resultant palindrome length : ", length)
}
func main() {
// Test
// iiii => 4
lengthOfLPS("nitiiiigi")
// ivfvi => 5
lengthOfLPS("vvvvivfvim")
// civic => 5
lengthOfLPS("xyzacivicxrs")
// opo => 3
lengthOfLPS("ttoopo")
}
Output
Given string : nitiiiigi
Resultant palindrome length : 4
Given string : vvvvivfvim
Resultant palindrome length : 5
Given string : xyzacivicxrs
Resultant palindrome length : 5
Given string : ttoopo
Resultant palindrome length : 3
<?php
// Php program for
// Longest palindromic substring recursive
class LongestPalindrome
{
public function maxValue($a, $b)
{
if ($a > $b)
{
return $a;
}
return $b;
}
public function maxPalindromicLength($text, $s, $e, $length)
{
if ($s == $e)
{
return $length + 1;
}
if ($s > $e)
{
return $length;
}
if ($text[$s] == $text[$e])
{
// When boundary element are similar.
// Find the palindrome length in possible three cases.
// Inner substring, start+1 to end and start to end-1
return $this->maxValue(
$this->maxPalindromicLength($text, $s + 1, $e - 1, $length + 2),
$this->maxValue($this->maxPalindromicLength($text, $s + 1, $e, 0),
$this->maxPalindromicLength($text, $s, $e - 1, 0)));
}
return $this->maxValue($this->maxPalindromicLength($text, $s + 1, $e, 0),
$this->maxPalindromicLength($text, $s, $e - 1, 0));
}
public function lengthOfLPS($text)
{
// Get length of text
$n = strlen($text);
if ($n == 0)
{
// When text is empty
return;
}
// Display given text
echo("\n Given string : ".$text);
// 1st parameters are passing text
// 2nd parameter is start point
// 3rd parameter is last point
// 4th is resultant length
$length = $this->maxPalindromicLength($text, 0, $n - 1, 0);
// Display length of resultant palindrome
echo("\n Resultant palindrome length : ".$length);
}
}
function main()
{
$task = new LongestPalindrome();
// Test
// iiii => 4
$task->lengthOfLPS("nitiiiigi");
// ivfvi => 5
$task->lengthOfLPS("vvvvivfvim");
// civic => 5
$task->lengthOfLPS("xyzacivicxrs");
// opo => 3
$task->lengthOfLPS("ttoopo");
}
main();
Output
Given string : nitiiiigi
Resultant palindrome length : 4
Given string : vvvvivfvim
Resultant palindrome length : 5
Given string : xyzacivicxrs
Resultant palindrome length : 5
Given string : ttoopo
Resultant palindrome length : 3
// Node JS program for
// Longest palindromic substring recursive
class LongestPalindrome
{
maxValue(a, b)
{
if (a > b)
{
return a;
}
return b;
}
maxPalindromicLength(text, s, e, length)
{
if (s == e)
{
return length + 1;
}
if (s > e)
{
return length;
}
if (text.charAt(s) == text.charAt(e))
{
// When boundary element are similar.
// Find the palindrome length in possible three cases.
// Inner substring, start+1 to end and start to end-1
return this.maxValue(
this.maxPalindromicLength(text, s + 1, e - 1, length + 2),
this.maxValue(this.maxPalindromicLength(text, s + 1, e, 0),
this.maxPalindromicLength(text, s, e - 1, 0)));
}
return this.maxValue(this.maxPalindromicLength(text, s + 1, e, 0),
this.maxPalindromicLength(text, s, e - 1, 0));
}
lengthOfLPS(text)
{
// Get length of text
var n = text.length;
if (n == 0)
{
// When text is empty
return;
}
// Display given text
process.stdout.write("\n Given string : " + text);
// 1st parameters are passing text
// 2nd parameter is start point
// 3rd parameter is last point
// 4th is resultant length
var length = this.maxPalindromicLength(text, 0, n - 1, 0);
// Display length of resultant palindrome
process.stdout.write("\n Resultant palindrome length : " + length);
}
}
function main()
{
var task = new LongestPalindrome();
// Test
// iiii => 4
task.lengthOfLPS("nitiiiigi");
// ivfvi => 5
task.lengthOfLPS("vvvvivfvim");
// civic => 5
task.lengthOfLPS("xyzacivicxrs");
// opo => 3
task.lengthOfLPS("ttoopo");
}
main();
Output
Given string : nitiiiigi
Resultant palindrome length : 4
Given string : vvvvivfvim
Resultant palindrome length : 5
Given string : xyzacivicxrs
Resultant palindrome length : 5
Given string : ttoopo
Resultant palindrome length : 3
# Python 3 program for
# Longest palindromic substring recursive
class LongestPalindrome :
def maxValue(self, a, b) :
if (a > b) :
return a
return b
def maxPalindromicLength(self, text, s, e, length) :
if (s == e) :
return length + 1
if (s > e) :
return length
if (text[s] == text[e]) :
# When boundary element are similar.
# Find the palindrome length in possible three cases.
# Inner substring, start+1 to end and start to end-1
return self.maxValue(
self.maxPalindromicLength(text, s + 1, e - 1, length + 2),
self.maxValue(self.maxPalindromicLength(text, s + 1, e, 0),
self.maxPalindromicLength(text, s, e - 1, 0)))
return self.maxValue(self.maxPalindromicLength(text, s + 1, e, 0),
self.maxPalindromicLength(text, s, e - 1, 0))
def lengthOfLPS(self, text) :
# Get length of text
n = len(text)
if (n == 0) :
# When text is empty
return
# Display given text
print("\n Given string : ", text, end = "")
# 1st parameters are passing text
# 2nd parameter is start point
# 3rd parameter is last point
# 4th is resultant length
length = self.maxPalindromicLength(text, 0, n - 1, 0)
# Display length of resultant palindrome
print("\n Resultant palindrome length : ", length, end = "")
def main() :
task = LongestPalindrome()
# Test
# iiii => 4
task.lengthOfLPS("nitiiiigi")
# ivfvi => 5
task.lengthOfLPS("vvvvivfvim")
# civic => 5
task.lengthOfLPS("xyzacivicxrs")
# opo => 3
task.lengthOfLPS("ttoopo")
if __name__ == "__main__": main()
Output
Given string : nitiiiigi
Resultant palindrome length : 4
Given string : vvvvivfvim
Resultant palindrome length : 5
Given string : xyzacivicxrs
Resultant palindrome length : 5
Given string : ttoopo
Resultant palindrome length : 3
# Ruby program for
# Longest palindromic substring recursive
class LongestPalindrome
def maxValue(a, b)
if (a > b)
return a
end
return b
end
def maxPalindromicLength(text, s, e, length)
if (s == e)
return length + 1
end
if (s > e)
return length
end
if (text[s] == text[e])
# When boundary element are similar.
# Find the palindrome length in possible three cases.
# Inner substring, start+1 to end and start to end-1
return self.maxValue(
self.maxPalindromicLength(text, s + 1, e - 1, length + 2),
self.maxValue(self.maxPalindromicLength(text, s + 1, e, 0),
self.maxPalindromicLength(text, s, e - 1, 0))
)
end
return self.maxValue(
self.maxPalindromicLength(text, s + 1, e, 0),
self.maxPalindromicLength(text, s, e - 1, 0))
end
def lengthOfLPS(text)
# Get length of text
n = text.length
if (n == 0)
# When text is empty
return
end
# Display given text
print("\n Given string : ", text)
# 1st parameters are passing text
# 2nd parameter is start point
# 3rd parameter is last point
# 4th is resultant length
length = self.maxPalindromicLength(text, 0, n - 1, 0)
# Display length of resultant palindrome
print("\n Resultant palindrome length : ", length)
end
end
def main()
task = LongestPalindrome.new()
# Test
# iiii => 4
task.lengthOfLPS("nitiiiigi")
# ivfvi => 5
task.lengthOfLPS("vvvvivfvim")
# civic => 5
task.lengthOfLPS("xyzacivicxrs")
# opo => 3
task.lengthOfLPS("ttoopo")
end
main()
Output
Given string : nitiiiigi
Resultant palindrome length : 4
Given string : vvvvivfvim
Resultant palindrome length : 5
Given string : xyzacivicxrs
Resultant palindrome length : 5
Given string : ttoopo
Resultant palindrome length : 3
import scala.collection.mutable._;
// Scala program for
// Longest palindromic substring recursive
class LongestPalindrome()
{
def maxValue(a: Int, b: Int): Int = {
if (a > b)
{
return a;
}
return b;
}
def maxPalindromicLength(
text: String,
s: Int,
e: Int,
length: Int): Int = {
if (s == e)
{
return length + 1;
}
if (s > e)
{
return length;
}
if (text.charAt(s) == text.charAt(e))
{
// When boundary element are similar.
// Find the palindrome length in possible three cases.
// Inner substring, start+1 to end and start to end-1
return maxValue(
maxPalindromicLength(text, s + 1, e - 1, length + 2),
maxValue(maxPalindromicLength(text, s + 1, e, 0),
maxPalindromicLength(text, s, e - 1, 0)));
}
return maxValue(maxPalindromicLength(text, s + 1, e, 0), maxPalindromicLength(text, s, e - 1, 0));
}
def lengthOfLPS(text: String): Unit = {
// Get length of text
var n: Int = text.length();
if (n == 0)
{
// When text is empty
return;
}
// Display given text
print("\n Given string : " + text);
// 1st parameters are passing text
// 2nd parameter is start point
// 3rd parameter is last point
// 4th is resultant length
var length: Int = maxPalindromicLength(text, 0, n - 1, 0);
// Display length of resultant palindrome
print("\n Resultant palindrome length : " + length);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: LongestPalindrome = new LongestPalindrome();
// Test
// iiii => 4
task.lengthOfLPS("nitiiiigi");
// ivfvi => 5
task.lengthOfLPS("vvvvivfvim");
// civic => 5
task.lengthOfLPS("xyzacivicxrs");
// opo => 3
task.lengthOfLPS("ttoopo");
}
}
Output
Given string : nitiiiigi
Resultant palindrome length : 4
Given string : vvvvivfvim
Resultant palindrome length : 5
Given string : xyzacivicxrs
Resultant palindrome length : 5
Given string : ttoopo
Resultant palindrome length : 3
import Foundation;
// Swift 4 program for
// Longest palindromic substring recursive
class LongestPalindrome
{
func maxValue(_ a: Int, _ b: Int) -> Int
{
if (a > b)
{
return a;
}
return b;
}
func maxPalindromicLength(_ text: [Character],
_ s: Int,
_ e: Int,
_ length: Int) -> Int
{
if (s == e)
{
return length + 1;
}
if (s > e)
{
return length;
}
if (text[s] == text[e])
{
// When boundary element are similar.
// Find the palindrome length in possible three cases.
// Inner substring, start+1 to end and start to end-1
return self.maxValue(
self.maxPalindromicLength(text, s + 1, e - 1, length + 2),
self.maxValue(self.maxPalindromicLength(text, s + 1, e, 0),
self.maxPalindromicLength(text, s, e - 1, 0)));
}
return self.maxValue(self.maxPalindromicLength(text, s + 1, e, 0),
self.maxPalindromicLength(text, s, e - 1, 0));
}
func lengthOfLPS(_ text: String)
{
// Get length of text
let n: Int = text.count;
if (n == 0)
{
// When text is empty
return;
}
// Display given text
print("\n Given string : ", text, terminator: "");
// 1st parameters are passing text
// 2nd parameter is start point
// 3rd parameter is last point
// 4th is resultant length
let length: Int = self.maxPalindromicLength(Array(text), 0, n - 1, 0);
// Display length of resultant palindrome
print("\n Resultant palindrome length : ", length, terminator: "");
}
}
func main()
{
let task: LongestPalindrome = LongestPalindrome();
// Test
// iiii => 4
task.lengthOfLPS("nitiiiigi");
// ivfvi => 5
task.lengthOfLPS("vvvvivfvim");
// civic => 5
task.lengthOfLPS("xyzacivicxrs");
// opo => 3
task.lengthOfLPS("ttoopo");
}
main();
Output
Given string : nitiiiigi
Resultant palindrome length : 4
Given string : vvvvivfvim
Resultant palindrome length : 5
Given string : xyzacivicxrs
Resultant palindrome length : 5
Given string : ttoopo
Resultant palindrome length : 3
// Kotlin program for
// Longest palindromic substring recursive
class LongestPalindrome
{
fun maxValue(a: Int, b: Int): Int
{
if (a > b)
{
return a;
}
return b;
}
fun maxPalindromicLength(text: String, s: Int, e: Int, length: Int): Int
{
if (s == e)
{
return length + 1;
}
if (s > e)
{
return length;
}
if (text.get(s) == text.get(e))
{
// When boundary element are similar.
// Find the palindrome length in possible three cases.
// Inner substring, start+1 to end and start to end-1
return this.maxValue(
this.maxPalindromicLength(text, s + 1, e - 1, length + 2),
this.maxValue(this.maxPalindromicLength(text, s + 1, e, 0),
this.maxPalindromicLength(text, s, e - 1, 0)));
}
return this.maxValue(this.maxPalindromicLength(text, s + 1, e, 0),
this.maxPalindromicLength(text, s, e - 1, 0));
}
fun lengthOfLPS(text: String): Unit
{
// Get length of text
val n: Int = text.length;
if (n == 0)
{
// When text is empty
return;
}
// Display given text
print("\n Given string : " + text);
// 1st parameters are passing text
// 2nd parameter is start point
// 3rd parameter is last point
// 4th is resultant length
val length: Int = this.maxPalindromicLength(text, 0, n - 1, 0);
// Display length of resultant palindrome
print("\n Resultant palindrome length : " + length);
}
}
fun main(args: Array < String > ): Unit
{
val task: LongestPalindrome = LongestPalindrome();
// Test
// iiii => 4
task.lengthOfLPS("nitiiiigi");
// ivfvi => 5
task.lengthOfLPS("vvvvivfvim");
// civic => 5
task.lengthOfLPS("xyzacivicxrs");
// opo => 3
task.lengthOfLPS("ttoopo");
}
Output
Given string : nitiiiigi
Resultant palindrome length : 4
Given string : vvvvivfvim
Resultant palindrome length : 5
Given string : xyzacivicxrs
Resultant palindrome length : 5
Given string : ttoopo
Resultant palindrome length : 3
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