Търся алгоритъм (в Java), който ще позволи на потребителя да въведе низ и програмата ще върне най-дългия квадратен подниз. Например, ако потребителят въведе „poofoofoopoo“, тогава програмата връща „Longest Square Substring: foofoo“. Ако някой може да напише такъв алгоритъм, ще бъда много благодарен!
Първата ми мисъл беше да модифицирам алгоритъма на Manacher, който връща най-дългия палиндромичен подниз (в линейно време).
Ето кода на Java, който имам за алгоритъма на Manacher:
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);
}
}