java - 最长方形子串算法

Question

我正在寻找一种算法(在 Java 中)，它允许用户输入一个字符串，程序将返回最长的方形子字符串。例如，如果用户输入“poofoofoopoo”，则程序返回“Longest Square Substring: foofoo”。如果有人能写出这样的算法，我将不胜感激!

我的第一个想法是修改返回最长回文子串(线性时间)的 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

然后遍历数组并查找相邻的条目 a 和 b where

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

与

d = abs(a - b)

然后是字符串

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

是候选人。确保在创建子字符串时不要超出字符串的末尾。