Longest palindromic substring manacher's algorithm
Manacher's algorithm is an efficient algorithm that can find the longest palindromic substring in a given string in linear time, i.e., O(n), where n is the length of the string.
The algorithm works by maintaining a palindrome center and its corresponding palindrome radius for each position in the string. It starts by initializing the palindrome center and radius for the first character, and then iterates through the string character by character, updating the palindrome centers and radii as needed.
The key insight behind Manacher's algorithm is that it takes advantage of the symmetry properties of palindromes to avoid redundant computation. In particular, it takes advantage of the fact that if a palindrome centered at position i extends to position j, then the palindrome centered at position i+k (where k<j-i) must have at least the same length as the palindrome centered at position i-k.
By using this property, the algorithm avoids computing palindromes that have already been computed, and thus can find the longest palindromic substring in linear time.
Here is a high-level overview of how the algorithm works:
Pre-process the input string by inserting special characters between each pair of adjacent characters, and at the beginning and end of the string. This ensures that all palindromes in the string are of odd length, which simplifies the algorithm.
Initialize the palindrome centers and radii for the first character in the string.
For each character in the string, determine its corresponding palindrome center and radius based on the previously computed centers and radii.
Keep track of the longest palindrome found so far, and update it as needed.
Once all characters in the string have been processed, remove the special characters from the longest palindrome found.
Here given code implementation process.
/*
C program for
Longest palindromic substring manacher's algorithm
*/
#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;
}
// When text not empty
// Increase n value
n = (2 *n) + 1;
// Declare some auxiliary variables
int left = 0;
int center = 1;
int right = 2;
int diff = -1;
int expand = -1;
int length = 0;
int point = 0;
int start = -1;
int end = -1;
int lps[n];
// Set initial two starting value
lps[0] = 0;
lps[1] = 1;
for (int i = 2; i < n; i++)
{
left = 2 *center - i;
expand = 0;
diff = right - i;
if (diff >= 0)
{
if (lps[left] < diff)
{
lps[i] = lps[left];
}
else if (lps[left] == diff && right == n - 1)
{
lps[i] = lps[left];
}
else if (lps[left] == diff && right < n - 1)
{
lps[i] = lps[left];
expand = 1;
}
else if (lps[left] > diff)
{
lps[i] = diff;
expand = 1;
}
}
else
{
lps[i] = 0;
expand = 1;
}
if (expand == 1)
{
while (((i + lps[i] + 1) < n &&
(i - lps[i]) > 0) &&
(((i + lps[i] + 1) % 2 == 0) ||
(text[(i + lps[i] + 1) / 2] == text[(i - lps[i] - 1) / 2])))
{
lps[i]++;
}
}
if (lps[i] > length)
{
length = lps[i];
point = i;
}
if (i + lps[i] > right)
{
center = i;
right = i + lps[i];
}
}
start = (point - length) / 2;
// 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
findLPS("nitiiiigi");
// ivfvi
findLPS("vvvvivfvim");
// civic
findLPS("xyzacivicxrs");
// opo
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 manacher's algorithm
public class LongestPalindrome
{
public void findLPS(String text)
{
// Get length of text
int n = text.length();
if (n == 0)
{
// When text is empty
return;
}
// When text not empty
// Increase n value
n = (2 * n) + 1;
// Declare some auxiliary variables
int left = 0;
int center = 1;
int right = 2;
int diff = -1;
int expand = -1;
int length = 0;
int point = 0;
int start = -1;
int end = -1;
int[] lps = new int[n];
// Set initial two starting value
lps[0] = 0;
lps[1] = 1;
for (int i = 2; i < n; i++)
{
left = 2 * center - i;
expand = 0;
diff = right - i;
if (diff >= 0)
{
if (lps[left] < diff)
{
lps[i] = lps[left];
}
else if (lps[left] == diff && right == n - 1)
{
lps[i] = lps[left];
}
else if (lps[left] == diff && right < n - 1)
{
lps[i] = lps[left];
expand = 1;
}
else if (lps[left] > diff)
{
lps[i] = diff;
expand = 1;
}
}
else
{
lps[i] = 0;
expand = 1;
}
if (expand == 1)
{
while (((i + lps[i] + 1) < n && ((i - lps[i]) > 0)) &&
(((i + lps[i] + 1) % 2 == 0) ||
(text.charAt((i + lps[i] + 1) / 2) ==
text.charAt((i - lps[i] - 1) / 2))))
{
lps[i]++;
}
}
if (lps[i] > length)
{
length = lps[i];
point = i;
}
if (i + lps[i] > right)
{
center = i;
right = i + lps[i];
}
}
start = (point - length) / 2;
// 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
task.findLPS("itiiiigi");
// ivfvi
task.findLPS("vvvvivfvim");
// civic
task.findLPS("xyzacivicxrs");
// opo
task.findLPS("ttoopo");
}
}
Output
Given string : itiiiigi
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 manacher's algorithm
class LongestPalindrome
{
public: void findLPS(string text)
{
// Get length of text
int n = text.length();
if (n == 0)
{
// When text is empty
return;
}
// When text not empty
// Increase n value
n = (2 *n) + 1;
// Declare some auxiliary variables
int left = 0;
int center = 1;
int right = 2;
int diff = -1;
int expand = -1;
int length = 0;
int point = 0;
int start = -1;
int end = -1;
int lps[n];
// Set initial two starting value
lps[0] = 0;
lps[1] = 1;
for (int i = 2; i < n; i++)
{
left = 2 *center - i;
expand = 0;
diff = right - i;
if (diff >= 0)
{
if (lps[left] < diff)
{
lps[i] = lps[left];
}
else if (lps[left] == diff && right == n - 1)
{
lps[i] = lps[left];
}
else if (lps[left] == diff && right < n - 1)
{
lps[i] = lps[left];
expand = 1;
}
else if (lps[left] > diff)
{
lps[i] = diff;
expand = 1;
}
}
else
{
lps[i] = 0;
expand = 1;
}
if (expand == 1)
{
while (((i + lps[i] + 1) < n && ((i - lps[i]) > 0)) &&
(((i + lps[i] + 1) % 2 == 0) ||
(text[(i + lps[i] + 1) / 2] == text[(i - lps[i] - 1) / 2])))
{
lps[i]++;
}
}
if (lps[i] > length)
{
length = lps[i];
point = i;
}
if (i + lps[i] > right)
{
center = i;
right = i + lps[i];
}
}
start = (point - length) / 2;
// 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
task->findLPS("itiiiigi");
// ivfvi
task->findLPS("vvvvivfvim");
// civic
task->findLPS("xyzacivicxrs");
// opo
task->findLPS("ttoopo");
return 0;
}
Output
Given string : itiiiigi
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 manacher's algorithm
public class LongestPalindrome
{
public void findLPS(String text)
{
// Get length of text
int n = text.Length;
if (n == 0)
{
// When text is empty
return;
}
// When text not empty
// Increase n value
n = (2 * n) + 1;
// Declare some auxiliary variables
int left = 0;
int center = 1;
int right = 2;
int diff = -1;
int expand = -1;
int length = 0;
int point = 0;
int start = -1;
int[] lps = new int[n];
// Set initial two starting value
lps[0] = 0;
lps[1] = 1;
for (int i = 2; i < n; i++)
{
left = 2 * center - i;
expand = 0;
diff = right - i;
if (diff >= 0)
{
if (lps[left] < diff)
{
lps[i] = lps[left];
}
else if (lps[left] == diff && right == n - 1)
{
lps[i] = lps[left];
}
else if (lps[left] == diff && right < n - 1)
{
lps[i] = lps[left];
expand = 1;
}
else if (lps[left] > diff)
{
lps[i] = diff;
expand = 1;
}
}
else
{
lps[i] = 0;
expand = 1;
}
if (expand == 1)
{
while (((i + lps[i] + 1) < n && ((i - lps[i]) > 0)) &&
(((i + lps[i] + 1) % 2 == 0) ||
(text[(i + lps[i] + 1) / 2] == text[(i - lps[i] - 1) / 2])))
{
lps[i]++;
}
}
if (lps[i] > length)
{
length = lps[i];
point = i;
}
if (i + lps[i] > right)
{
center = i;
right = i + lps[i];
}
}
start = (point - length) / 2;
// 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
task.findLPS("itiiiigi");
// ivfvi
task.findLPS("vvvvivfvim");
// civic
task.findLPS("xyzacivicxrs");
// opo
task.findLPS("ttoopo");
}
}
Output
Given string : itiiiigi
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 manacher's algorithm
func findLPS(text string) {
// Get length of text
var n int = len(text)
if n == 0 {
// When text is empty
return
}
// When text not empty
// Increase n value
n = (2 * n) + 1
// Declare some auxiliary variables
var left int = 0
var center int = 1
var right int = 2
var diff int = -1
var expand int = -1
var length int = 0
var point int = 0
var start int = -1
var lps = make([] int, n)
// Set initial two starting value
lps[0] = 0
lps[1] = 1
for i := 2 ; i < n ; i++ {
left = 2 * center - i
expand = 0
diff = right - i
if diff >= 0 {
if lps[left] < diff {
lps[i] = lps[left]
} else if lps[left] == diff && right == n - 1 {
lps[i] = lps[left]
} else if lps[left] == diff && right < n - 1 {
lps[i] = lps[left]
expand = 1
} else if lps[left] > diff {
lps[i] = diff
expand = 1
}
} else {
lps[i] = 0
expand = 1
}
if expand == 1 {
for (((i + lps[i] + 1) < n && ((i - lps[i]) > 0)) && (((i + lps[i] + 1) % 2 == 0) || (text[(i + lps[i] + 1) / 2] == text[(i - lps[i] - 1) / 2]))) {
lps[i]++
}
}
if lps[i] > length {
length = lps[i]
point = i
}
if i + lps[i] > right {
center = i
right = i + lps[i]
}
}
start = (point - length) / 2
// 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(text[i])
}
// Display length of resultant palindrome
fmt.Print("\n Resultant length : ", length)
}
func main() {
// Test
// iiii
findLPS("itiiiigi")
// ivfvi
findLPS("vvvvivfvim")
// civic
findLPS("xyzacivicxrs")
// opo
findLPS("ttoopo")
}
Output
Given string : itiiiigi
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 manacher's algorithm
class LongestPalindrome
{
public function findLPS($text)
{
// Get length of text
$n = strlen($text);
if ($n == 0)
{
// When text is empty
return;
}
// When text not empty
// Increase n value
$n = (2 * $n) + 1;
// Declare some auxiliary variables
$left = 0;
$center = 1;
$right = 2;
$diff = -1;
$expand = -1;
$length = 0;
$point = 0;
$start = -1;
$lps = array_fill(0, $n, 0);
// Set initial two starting value
$lps[0] = 0;
$lps[1] = 1;
for ($i = 2; $i < $n; $i++)
{
$left = 2 * $center - $i;
$expand = 0;
$diff = $right - $i;
if ($diff >= 0)
{
if ($lps[$left] < $diff)
{
$lps[$i] = $lps[$left];
}
else if ($lps[$left] == $diff && $right == $n - 1)
{
$lps[$i] = $lps[$left];
}
else if ($lps[$left] == $diff && $right < $n - 1)
{
$lps[$i] = $lps[$left];
$expand = 1;
}
else if ($lps[$left] > $diff)
{
$lps[$i] = $diff;
$expand = 1;
}
}
else
{
$lps[$i] = 0;
$expand = 1;
}
if ($expand == 1)
{
while ((($i + $lps[$i] + 1) < $n &&
(($i - $lps[$i]) > 0)) &&
((($i + $lps[$i] + 1) % 2 == 0) ||
($text[(int)(($i + $lps[$i] + 1) / 2)] ==
$text[(int)(($i - $lps[$i] - 1) / 2)])))
{
$lps[$i]++;
}
}
if ($lps[$i] > $length)
{
$length = $lps[$i];
$point = $i;
}
if ($i + $lps[$i] > $right)
{
$center = $i;
$right = $i + $lps[$i];
}
}
$start = (int)(($point - $length) / 2);
// 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
$task->findLPS("itiiiigi");
// ivfvi
$task->findLPS("vvvvivfvim");
// civic
$task->findLPS("xyzacivicxrs");
// opo
$task->findLPS("ttoopo");
}
main();
Output
Given string : itiiiigi
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 manacher's algorithm
class LongestPalindrome
{
findLPS(text)
{
// Get length of text
var n = text.length;
if (n == 0)
{
// When text is empty
return;
}
// When text not empty
// Increase n value
n = (2 * n) + 1;
// Declare some auxiliary variables
var left = 0;
var center = 1;
var right = 2;
var diff = -1;
var expand = -1;
var length = 0;
var point = 0;
var start = -1;
var lps = Array(n).fill(0);
// Set initial two starting value
lps[0] = 0;
lps[1] = 1;
for (var i = 2; i < n; i++)
{
left = 2 * center - i;
expand = 0;
diff = right - i;
if (diff >= 0)
{
if (lps[left] < diff)
{
lps[i] = lps[left];
}
else if (lps[left] == diff && right == n - 1)
{
lps[i] = lps[left];
}
else if (lps[left] == diff && right < n - 1)
{
lps[i] = lps[left];
expand = 1;
}
else if (lps[left] > diff)
{
lps[i] = diff;
expand = 1;
}
}
else
{
lps[i] = 0;
expand = 1;
}
if (expand == 1)
{
while (((i + lps[i] + 1) < n &&
((i - lps[i]) > 0)) &&
(((i + lps[i] + 1) % 2 == 0) ||
(text.charAt(parseInt((i + lps[i] + 1) / 2))
== text.charAt(parseInt((i - lps[i] - 1) / 2)))))
{
lps[i]++;
}
}
if (lps[i] > length)
{
length = lps[i];
point = i;
}
if (i + lps[i] > right)
{
center = i;
right = i + lps[i];
}
}
start = parseInt((point - length) / 2);
// 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
task.findLPS("itiiiigi");
// ivfvi
task.findLPS("vvvvivfvim");
// civic
task.findLPS("xyzacivicxrs");
// opo
task.findLPS("ttoopo");
}
main();
Output
Given string : itiiiigi
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 manacher's algorithm
class LongestPalindrome :
def findLPS(self, text) :
# Get length of text
n = len(text)
if (n == 0) :
# When text is empty
return
# When text not empty
# Increase n value
n = (2 * n) + 1
# Declare some auxiliary variables
left = 0
center = 1
right = 2
diff = -1
expand = -1
length = 0
point = 0
start = -1
lps = [0] * (n)
# Set initial two starting value
lps[0] = 0
lps[1] = 1
i = 2
while (i < n) :
left = 2 * center - i
expand = 0
diff = right - i
if (diff >= 0) :
if (lps[left] < diff) :
lps[i] = lps[left]
elif (lps[left] == diff and right == n - 1) :
lps[i] = lps[left]
elif (lps[left] == diff and right < n - 1) :
lps[i] = lps[left]
expand = 1
elif (lps[left] > diff) :
lps[i] = diff
expand = 1
else :
lps[i] = 0
expand = 1
if (expand == 1) :
while (((i + lps[i] + 1) < n and
((i - lps[i]) > 0)) and
(((i + lps[i] + 1) % 2 == 0) or
(text[int((i + lps[i] + 1) / 2)] ==
text[int((i - lps[i] - 1) / 2)]))) :
lps[i] += 1
if (lps[i] > length) :
length = lps[i]
point = i
if (i + lps[i] > right) :
center = i
right = i + lps[i]
i += 1
start = int((point - length) / 2)
# 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
task.findLPS("itiiiigi")
# ivfvi
task.findLPS("vvvvivfvim")
# civic
task.findLPS("xyzacivicxrs")
# opo
task.findLPS("ttoopo")
if __name__ == "__main__": main()
Output
Given string : itiiiigi
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 manacher's algorithm
class LongestPalindrome
def findLPS(text)
# Get length of text
n = text.length
if (n == 0)
# When text is empty
return
end
# When text not empty
# Increase n value
n = (2 * n) + 1
# Declare some auxiliary variables
left = 0
center = 1
right = 2
diff = -1
expand = -1
length = 0
point = 0
start = -1
lps = Array.new(n) {0}
# Set initial two starting value
lps[0] = 0
lps[1] = 1
i = 2
while (i < n)
left = 2 * center - i
expand = 0
diff = right - i
if (diff >= 0)
if (lps[left] < diff)
lps[i] = lps[left]
elsif (lps[left] == diff && right == n - 1)
lps[i] = lps[left]
elsif (lps[left] == diff && right < n - 1)
lps[i] = lps[left]
expand = 1
elsif (lps[left] > diff)
lps[i] = diff
expand = 1
end
else
lps[i] = 0
expand = 1
end
if (expand == 1)
while (((i + lps[i] + 1) < n && ((i - lps[i]) > 0)) &&
(((i + lps[i] + 1) % 2 == 0) ||
(text[(i + lps[i] + 1) / 2] ==
text[(i - lps[i] - 1) / 2])))
lps[i] += 1
end
end
if (lps[i] > length)
length = lps[i]
point = i
end
if (i + lps[i] > right)
center = i
right = i + lps[i]
end
i += 1
end
start = (point - length) / 2
# 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
task.findLPS("itiiiigi")
# ivfvi
task.findLPS("vvvvivfvim")
# civic
task.findLPS("xyzacivicxrs")
# opo
task.findLPS("ttoopo")
end
main()
Output
Given string : itiiiigi
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 manacher's algorithm
class LongestPalindrome()
{
def findLPS(text: String): Unit = {
// Get length of text
var n: Int = text.length();
if (n == 0)
{
// When text is empty
return;
}
// When text not empty
// Increase n value
n = (2 * n) + 1;
// Declare some auxiliary variables
var left: Int = 0;
var center: Int = 1;
var right: Int = 2;
var diff: Int = -1;
var expand: Int = -1;
var length: Int = 0;
var point: Int = 0;
var start: Int = -1;
var lps: Array[Int] = Array.fill[Int](n)(0);
// Set initial two starting value
lps(0) = 0;
lps(1) = 1;
var i: Int = 2;
while (i < n)
{
left = 2 * center - i;
expand = 0;
diff = right - i;
if (diff >= 0)
{
if (lps(left) < diff)
{
lps(i) = lps(left);
}
else if (lps(left) == diff && right == n - 1)
{
lps(i) = lps(left);
}
else if (lps(left) == diff && right < n - 1)
{
lps(i) = lps(left);
expand = 1;
}
else if (lps(left) > diff)
{
lps(i) = diff;
expand = 1;
}
}
else
{
lps(i) = 0;
expand = 1;
}
if (expand == 1)
{
while (((i + lps(i) + 1) < n &&
((i - lps(i)) > 0)) &&
(((i + lps(i) + 1) % 2 == 0) ||
(text.charAt((i + lps(i) + 1) / 2) ==
text.charAt((i - lps(i) - 1) / 2))))
{
lps(i) += 1;
}
}
if (lps(i) > length)
{
length = lps(i);
point = i;
}
if (i + lps(i) > right)
{
center = i;
right = i + lps(i);
}
i += 1;
}
start = (point - length) / 2;
// 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
task.findLPS("itiiiigi");
// ivfvi
task.findLPS("vvvvivfvim");
// civic
task.findLPS("xyzacivicxrs");
// opo
task.findLPS("ttoopo");
}
}
Output
Given string : itiiiigi
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 manacher's algorithm
class LongestPalindrome
{
func findLPS(_ data: String)
{
let text = Array(data);
// Get length of text
var n: Int = text.count;
if (n == 0)
{
// When text is empty
return;
}
// When text not empty
// Increase n value
n = (2 * n) + 1;
// Declare some auxiliary variables
var left: Int = 0;
var center: Int = 1;
var right: Int = 2;
var diff: Int = -1;
var expand: Int = -1;
var length: Int = 0;
var point: Int = 0;
var start: Int = -1;
var lps: [Int] = Array(repeating: 0, count: n);
// Set initial two starting value
lps[0] = 0;
lps[1] = 1;
var i: Int = 2;
while (i < n)
{
left = 2 * center - i;
expand = 0;
diff = right - i;
if (diff >= 0)
{
if (lps[left] < diff)
{
lps[i] = lps[left];
}
else if (lps[left] == diff && right == n - 1)
{
lps[i] = lps[left];
}
else if (lps[left] == diff && right < n - 1)
{
lps[i] = lps[left];
expand = 1;
}
else if (lps[left] > diff)
{
lps[i] = diff;
expand = 1;
}
}
else
{
lps[i] = 0;
expand = 1;
}
if (expand == 1)
{
while (((i + lps[i] + 1) < n &&
((i - lps[i]) > 0)) &&
(((i + lps[i] + 1) % 2 == 0) ||
(text[(i + lps[i] + 1) / 2] ==
text[(i - lps[i] - 1) / 2])))
{
lps[i] += 1;
}
}
if (lps[i] > length)
{
length = lps[i];
point = i;
}
if (i + lps[i] > right)
{
center = i;
right = i + lps[i];
}
i += 1;
}
start = (point - length) / 2;
// 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
task.findLPS("itiiiigi");
// ivfvi
task.findLPS("vvvvivfvim");
// civic
task.findLPS("xyzacivicxrs");
// opo
task.findLPS("ttoopo");
}
main();
Output
Given string : itiiiigi
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 manacher's algorithm
class LongestPalindrome
{
fun findLPS(text: String): Unit
{
// Get length of text
var n: Int = text.length;
if (n == 0)
{
// When text is empty
return;
}
// When text not empty
// Increase n value
n = (2 * n) + 1;
// Declare some auxiliary variables
var left: Int ;
var center: Int = 1;
var right: Int = 2;
var diff: Int ;
var expand: Int ;
var length: Int = 0;
var point: Int = 0;
var start: Int ;
var lps: Array < Int > = Array(n)
{
0
};
// Set initial two starting value
lps[0] = 0;
lps[1] = 1;
var i: Int = 2;
while (i < n)
{
left = 2 * center - i;
expand = 0;
diff = right - i;
if (diff >= 0)
{
if (lps[left] < diff)
{
lps[i] = lps[left];
}
else if (lps[left] == diff && right == n - 1)
{
lps[i] = lps[left];
}
else if (lps[left] == diff && right < n - 1)
{
lps[i] = lps[left];
expand = 1;
}
else if (lps[left] > diff)
{
lps[i] = diff;
expand = 1;
}
}
else
{
lps[i] = 0;
expand = 1;
}
if (expand == 1)
{
while (((i + lps[i] + 1) < n &&
((i - lps[i]) > 0)) &&
(((i + lps[i] + 1) % 2 == 0) ||
(text.get((i + lps[i] + 1) / 2) ==
text.get((i - lps[i] - 1) / 2))))
{
lps[i] += 1;
}
}
if (lps[i] > length)
{
length = lps[i];
point = i;
}
if (i + lps[i] > right)
{
center = i;
right = i + lps[i];
}
i += 1;
}
start = (point - length) / 2;
// 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
task.findLPS("itiiiigi");
// ivfvi
task.findLPS("vvvvivfvim");
// civic
task.findLPS("xyzacivicxrs");
// opo
task.findLPS("ttoopo");
}
Output
Given string : itiiiigi
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
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