Algorithm for Longest Square Substring

Question

I am seeking an algorithm (in Java) that will allow user to input a string and the program will return the longest square substring. For example, if user inputs 'poofoofoopoo' then the program returns 'Longest Square Substring: foofoo'. If anyone can write such an algorithm, I would be very appreciative!

My first thought was to modify the Manacher algorithm which returns the longest palindromic substring (in linear time).

Here is the Java code that I have for the Manacher algorithm:

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class LongestPalindrome 
{
	// function to pre-process string 
	public String preProcess(String str) 
	{
		int len = str.length();
		if (len == 0)
		{
			return "^$";
		}
		String s = "^";
		for (int i = 0; i < len; i++)
		{
			s += "#" + str.charAt(i);    
		}
		s += "#$";
		return s;
	}
	
	// function to get largest palindrome sub-string 
	public String getLongestPalindrome(String str)
	{
		// pre-process string 
		char[] s = preProcess(str).toCharArray();
		int N = s.length;
		int[] p = new int[N + 1];
		int id = 0; 
		int mx = 0;
		for (int i = 1; i < N - 1; i++) 
		{
			p[i] = 0;
			while (s[i + 1 + p[i]] == s[i - 1 - p[i]])
			{
				p[i]++;
			}
			if (i + p[i] > mx) 
			{
				mx = i + p[i];
				id = i;
			}
		}
		// length of largest palindrome 
		int maxLen = 0;
		// position of center of largest palindrome 
		int centerIndex = 0;
		for (int i = 1; i < N - 1; i++) 
		{
			if (p[i] > maxLen) 
			{
				maxLen = p[i];
				centerIndex = i;
			}
		}
		// starting index of palindrome 
		int pos = (centerIndex - 1 - maxLen)/2;
		return str.substring(pos , pos + maxLen);        
	}
	
	// Main Function
	public static void main(String[] args) throws IOException
	{    
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		System.out.println("LongestPalindrome Algorithm Test\n");
		System.out.println("\nEnter String");
		String text = br.readLine();
		
		LongestPalindrome m = new LongestPalindrome(); 
		String LongestPalindrome = m.getLongestPalindrome(text); 
		System.out.println("\nLongest Palindrome: "+ LongestPalindrome);    
	}    
}

M Oehm M Oehm · Accepted Answer · 2015-03-06T09:14:39

Adjacent substrings and palindromes are quite different, I think.

One method to find the longest adjacent substring is to keep an array of indices. At the beginning, this is just an enumeration from 0 to (but not including) str.length. Sort this array, such that

str.substr(a) < str.substr(b)

which in your example yields:

[3]     foofoopoo
[6]     foopoo
[2]     ofoofoopoo
[5]     ofoopoo
[1]     oofoofoopoo
[4]     oofoopoo
[7]     oopoo
[8]     opoo
[9]     poo
[0]     poofoofoopoo
[11]    o
[10]    oo

Then walk through the array and look for adjacent entries a and b where

str.substr(a, a + d) == str.substr(b, b + d)

with

d = abs(a - b)

Then the string

str.substr(min(a, b), min(a, b) + 2 * d)

is a candidate. Make sure not to go beyond the string's end when creating substrings.

Algorithm for Longest Square Substring

1 Answers