最长平方子串算法

Question

我的第一个想法是修改Manacher算法，它返回最长的回文子字符串（在线性时间内）。

下面是Manacher算法的Java代码：

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);    
	}    
}

Answer 1

相邻的子串和回文有很大的不同，我认为。

查找最长相邻子字符串的一种方法是保留索引数组。开始时，这只是从0到（但不包括）str.length的枚举。对此数组进行排序，使

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

在您的示例中产生：

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

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

d = abs(a - b)

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