作为 HackerRank challenge 的一部分，我一整天都在尝试解决循环回文的问题。 .
传统的回文问题基本上是在一个更大的字符串中找到最长的对称子串(回文)的长度。在这个hackerRank challenge ，较大的字符串的长度限制为 105。它还要求我们找到每个旋转字符串的长度，从而增加了另一层复杂性。
已发布类似问题here ，但我无法提取足够的信息来让我的代码足够快运行。
我编写了以下 Java 代码，它是对 Manacher's algorithm 的修改在旋转上下文中:
package cards.myb.algorithms;
import java.io.*;
import java.util.*;
import java.text.*;
import java.lang.management.ManagementFactory;
import java.lang.management.ThreadMXBean;
import java.math.*;
import java.util.regex.*;
public class CircularPalindrome {
public static void main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
boolean use_manacher = true;
int N = 0;
String S = "";
String inputFile = "D:\\Home\\Java\\AlgorithmPractice\\input16.txt";
String solutionFile = "D:\\Home\\Java\\AlgorithmPractice\\output16.txt";
System.out.println("Reading file " + inputFile);
File file = new File(inputFile);
try {
FileInputStream fis = new FileInputStream(file);
BufferedReader in = new BufferedReader(new InputStreamReader(fis));
N = Integer.valueOf(in.readLine());
S = in.readLine();
in.close();
} catch(IOException e) {
e.printStackTrace();
return;
}
// Convert string to char for efficiency
char[] sArr = S.toCharArray();
// Start timer
ThreadMXBean threadMXBean = ManagementFactory.getThreadMXBean();
long tStartNS = threadMXBean.getCurrentThreadCpuTime();
System.out.println("Starting clock");
// Allocate space for Sk, k=0...N-1
int[] lengths = new int[N];
int[] plenEvenArr = new int[N];
int[] plenOddArr = new int[N];
// ********************************************
// Part 1 : Even palindromes
// ********************************************
int best_right = N-1, best_left = 0, best_plen = 0;
for(int i=0; i<N; i++) {
// i points to the position at the palindrome center (between two elements)
boolean do_loop = true;
int left, right, plen;
// Mirror image optimization
// Manacher's algorithm
if(!use_manacher || i > best_right) {
left = i;
right = (i-1+N)%N;
plen = 0;
//System.out.println("plen=" + plen + ", right=" + right + ", left=" + left);
} else {
int i2 = (best_left + best_right - i + 1 + N) % N;
//System.out.println("i=" + i + ", best_left = " + best_left + ", best_right=" + best_right + ", i2=" + i2);
if(i2 >= i) {
left = i;
right = (i-1+N)%N;
plen = 0;
//System.out.println("plen=" + plen + ", right=" + right + ", left=" + left);
} else if(plenEvenArr[i2] < ((best_right - i + 1 + N) % N) * 2) {
plen = plenEvenArr[i2];
do_loop = false;
left = right = 0; // Avoid warnings
//System.out.println("use mirror image plenArr[i2]=" + plenArr[i2]);
} else {
plen = ((best_right - i + 1 + N) % N) * 2;
right = best_right;
left = (best_right - plen + 1 + N) % N;
//System.out.println("start from plen=" + plen + ", right=" + right + ", left=" + left);
}
}
// Find maximum even palindrome with center at i
for(; do_loop && plen < N-1; plen += 2) {
char expandleft = sArr[(left - 1 + N) % N];
char expandright = sArr[(right + 1) % N];
if(expandleft == expandright) {
left = (left - 1 + N) % N;
right = (right + 1) % N;
} else
break;
}
plenEvenArr[i] = plen;
// Keep track of best
if(plen > best_plen) {
best_right = right;
best_left = left;
best_plen = plen;
}
}
long tEvenNS = threadMXBean.getCurrentThreadCpuTime();
// ********************************************
// Part 2 : Odd palindromes
// ********************************************
best_right = 0; best_left = 0; best_plen = 1;
for(int i=0; i<N; i++) {
// i points to the middle element of the palindrome
boolean do_loop = true;
int left, right, plen;
// Mirror image optimization
// Manacher's algorithm
if(!use_manacher || i > best_right) {
left = right = i;
plen = 1;
// System.out.println("plen=" + plen + ", right=" + right + ", left=" + left);
} else {
int dist_to_best_right = (best_right - i + N) % N;
int i2 = (best_left + dist_to_best_right) % N;
int plen_best = dist_to_best_right * 2 + 1;
// System.out.println("i=" + i + ", best_left = " + best_left + ", dist_to_best_right=" + dist_to_best_right + ", best_right=" + best_right + ", i2=" + i2);
if(i2 >= i) {
left = right = i;
plen = 1;
// System.out.println("plen=" + plen + ", right=" + right + ", left=" + left);
} else if(plenOddArr[i2] < plen_best) {
plen = plenOddArr[i2];
do_loop = false;
left = right = 0; // Avoid warnings
// System.out.println("use mirror image plenArr[i2]=" + plenArr[i2]);
} else {
plen = plen_best;
right = best_right;
left = (i - dist_to_best_right + N) % N;
// System.out.println("start from plen=" + plen + ", right=" + right + ", left=" + left);
}
}
// Find maximum odd palindrome with center character at i
for(; plen < N-1 && do_loop; plen += 2) {
char expandleft = sArr[(left - 1 + N) % N];
char expandright = sArr[(right + 1) % N];
if(expandleft == expandright) {
left = (left - 1 + N) % N;
right = (right + 1) % N;
} else
break;
}
plenOddArr[i] = plen;
// Keep track of best
if(plen > best_plen) {
best_right = right;
best_left = left;
best_plen = plen;
}
}
long tOddNS = threadMXBean.getCurrentThreadCpuTime();
// ********************************************
// Part 3 : Find maximum palindrome for Sk
// ********************************************
for(int i=0; i<N; i++)
lengths[i] = 1;
for(int i=0; i<N; i++) {
int plenEven = plenEvenArr[i];
if(plenEven > 1) {
for(int k=0; k<N; k++) {
// Calculate length of the palindrome in Sk
int spaceLeft = (i >= k) ? (i - k) : (N + i - k);
int spaceRight = (i > k) ? (N + k - i) : (k - i);
// Corner case: i=k and plen=N
int len;
if(i==k && plenEven == N)
len = plenEven;
else
len = Math.min(plenEven, Math.min(spaceLeft*2, spaceRight*2));
// Update array
lengths[k] = Math.max(lengths[k], len);
}
}
}
for(int i=0; i<N; i++) {
int plenOdd = plenOddArr[i];
if(plenOdd > 1) {
for(int k=0; k<N; k++) {
// Calculate length of the palindrome in Sk
int spaceLeft = (i >= k) ? (i - k) : (N + i - k);
int spaceRight = (i >= k) ? (N + k - i - 1) : (k - i - 1);
int len = Math.min(plenOdd, Math.min(spaceLeft*2+1, spaceRight*2+1));
// Update array
lengths[k] = Math.max(lengths[k], len);
}
}
}
// End timer
long tEndNS = threadMXBean.getCurrentThreadCpuTime();
System.out.println("Clock stopped");
// Print result
for(int i=0; i<N; i++) {
System.out.println(lengths[i]);
}
// Read solution from file
int[] solution = new int[N];
System.out.println("Reading solution file " + solutionFile);
File solfile = new File(solutionFile);
try {
BufferedReader solin = new BufferedReader(new InputStreamReader(new FileInputStream(solfile)));
for(int i=0; i<N; i++) {
solution[i] = Integer.valueOf(solin.readLine());
}
solin.close();
} catch(IOException e) {
e.printStackTrace();
return;
}
// Check solution correctness
boolean correct = true;
for(int i=0; i<N; i++) {
if(lengths[i] != solution[i]) {
System.out.println(String.format("Mismatch to solution: lengths[%d] = %d (should be %d)", i, lengths[i], solution[i]));
correct = false;
}
}
if(correct)
System.out.println("Solution is correct");
// Calculate/print total elapsed time
System.out.println(String.format("Total CPU time : %.6f sec", (float)(tEndNS - tStartNS) / 1.0e9));
System.out.println(String.format(" Even palindromes took %.6f sec", (float)(tEvenNS - tStartNS) / 1.0e9));
System.out.println(String.format(" Odd palindromes took %.6f sec", (float)(tOddNS - tEvenNS) / 1.0e9));
System.out.println(String.format(" Length calculation took %.6f sec", (float)(tEndNS - tOddNS) / 1.0e9));
}
}
它工作正常，但速度不够快。以下是“use_manacher=true”和 HackerRank 输入文件 input16.txt 的结果，这是一个复杂的测试用例，几乎有 105 个字符。
Solution is correct
Total CPU time : 79.841313 sec
Even palindromes took 18.220917 sec
Odd palindromes took 16.738907 sec
Length calculation took 44.881486 sec
“解决方案是正确的”意味着输出与 HackerRank 提供的匹配。使用“use_manacher=false”，以便它回退到一个简单的 O(n2) 算法，我们从每个可能的中心点开始，并向两侧扩展，直到我们达到字符串的长度我们有:
Total CPU time : 85.582152 sec
Even palindromes took 20.451731 sec
Odd palindromes took 20.389331 sec
Length calculation took 44.741087 sec
最让我吃惊的是，使用 Manacher 的算法进行优化在循环上下文中并没有太大帮助(仅 10-20% 的增益)。此外，与将回文映射到旋转字符串中的长度(~45 秒)相比，在圆形数组中查找回文(~35 秒)花费的时间更少。
在 HackerRank 上有 100 多个成功提交并获得满分，我认为这意味着应该有一个解决方案可以在典型 CPU 上在 10 秒内解决相同的问题:)
最佳答案
这仍然很慢......我所知道的是不要使用递归回文检查
即
static boolean isPali(String s) {
if (s.length() == 0 || s.length() == 1)
return true;
if (s.charAt(0) == s.charAt(s.length() - 1))
return isPali(s.substring(1, s.length() - 1));
return false;
}
这是我的回答:
import java.io.*;
import java.util.*;
public class Solution {
// I found this on stackoverflow it was about 3 times faster for a test I ran
static boolean isPali(String str){
StringBuilder sb = new StringBuilder(str);
return str.equals(sb.reverse().toString());
}
static int subs(String s){
int max=0;
for(int j = 0 ; j < s.length(); j++ ) {
for (int i = 1; i <= s.length() - j; i++) {
String sub = s.substring(j, j+i);
if(isPali(sub) && sub.length()>max){
max = sub.length();
}
}
}
return max;
}
static void rotation(int k,String s) {
for (int i = 0; i < k; i++) System.out.println(subs(s.substring(i, k) +s.substring(0, i)));
}
public static void main(String args[]) {
Scanner in = new Scanner(System.in);
int k = in.nextInt();
String s = in.next();
rotation(k,s);
}
}
关于java - 循环回文，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/38658847/