Skip to main content

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:

  1. 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.

  2. Initialize the palindrome centers and radii for the first character in the string.

  3. For each character in the string, determine its corresponding palindrome center and radius based on the previously computed centers and radii.

  4. Keep track of the longest palindrome found so far, and update it as needed.

  5. 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
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