我试图弄清楚如何解决 ACM ICPC 决赛之一中的一个问题（从 2012 年开始，所以我猜是最近的）。它被称为斐波那契词，在问题 D 下进行了描述。
我想我已经很接近了，因为除了最后一个之外的所有测试用例都给出了正确的答案。但最后，我得到了 6440026026380244497，它处于正确的数量级，但仍然相差甚远——因为数量级很大。:)
这是我的 Java 代码，有很多注释（你认为太多了？可以重构吗？）：
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class FibonacciWords {
public static StringBuilder[] updateChars(StringBuilder lastOneBack, StringBuilder firstTwoBack, StringBuilder lastTwoBack, StringBuilder firstThreeBack) {
int pattLen = lastOneBack.length();
StringBuilder[] newChars = new StringBuilder[2];
newChars[0] = new StringBuilder(pattLen); // will become the new lastOneBack!
newChars[1] = new StringBuilder(pattLen); // will become the new firstTwoBack!
if(lastOneBack.charAt(0) == 'E') { // lastOneBack not full yet
int shiftCharsBy = 0; // holds amount to shift lastOneBack by
for(int i = 0; i < pattLen; i++) {
if(firstTwoBack.charAt(i) != 'E') {
shiftCharsBy++; // need to move whatever is at beginning of firstTwoBack to end of lastOneBack
} else {
break; // when first 'E' is reached in firstTwoBack, the rest are 'E' also
}
}
for(int i = 0; i < pattLen-shiftCharsBy; i++) {
newChars[0].append(lastOneBack.charAt(i+shiftCharsBy)); // shift lastOneBack by shiftCharsBy characters
}
for(int i = 0; i < shiftCharsBy; i++) {
newChars[0].append(firstTwoBack.charAt(i)); // fill remainder of new lastOneBack with what's in firstTwoBack
}
} else { // lastOneBack already full
newChars[0] = lastTwoBack; // make lastOneBack lastTwoBack (following pattern)
}
if(firstTwoBack.charAt(pattLen-1) == 'E') { // firstTwoBack not full yet
if(lastOneBack.charAt(0) == 'E') {
for(int i = 1; i < pattLen; i++) {
if(lastOneBack.charAt(i) != 'E') {
newChars[1].append(lastOneBack.substring(i)); // move last characters of lastOneBack to front of new firstTwoBack
break;
}
}
int charsAdded = newChars[1].length();
for(int i = 0; i < pattLen-charsAdded; i++) {
newChars[1].append('E'); // fill whatever might remain with 'E'
}
} else {
//newChars[1] = lastOneBack;
for(int i = 0; i < pattLen; i++) {
if(firstTwoBack.charAt(i) != 'E') {
newChars[1].append(firstTwoBack.charAt(i));
} else {
break;
}
}
int charsAdded = newChars[1].length();
// now take from firstThreeBack--which also isn't full if firstTwoBack isn't--until pattLen is reached
for(int i = 0; i < pattLen-charsAdded; i++) {
newChars[1].append(firstThreeBack.charAt(i));
}
}
} else {
newChars[1] = firstTwoBack; // firstTwoBack doesn't change when already full
}
return newChars;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String pattern = br.readLine();
long numPattTwoPrior = 0; // number of times pattern occurred in F(n-2)
if(pattern.equals("0")) {
numPattTwoPrior++; // since n starts at 2 below, increment this if pattern is F(0), or "0"
}
long numPattOnePrior = 0; // number of times pattern occurred in F(n-1)
if(pattern.equals("1")) {
numPattOnePrior++; // since n starts at 2 below, increment this if pattern is F(1), or "1"
}
int pattLen = pattern.length();
StringBuilder lastCharsInOnePrior = new StringBuilder(pattLen); // keeps track of last pattLen characters in F(n-1)
for(int i = 0; i < pattLen; i++) {
lastCharsInOnePrior.append('E'); // 'E' stands for empty
}
lastCharsInOnePrior.setCharAt(pattLen-1, '1'); // since F(1) = "1"
StringBuilder firstCharsInTwoPrior = new StringBuilder(pattLen);
for(int i = 0; i < pattLen; i++) {
firstCharsInTwoPrior.append('E');
}
firstCharsInTwoPrior.setCharAt(0, '0'); // since F(0) = "0"
StringBuilder lastCharsInTwoPrior = null; // last characters always the same as 2 back, so keep track of this
StringBuilder firstCharsInThreePrior = null; // used for special case in updateChars
// number of times pattern occurs in F(n)
long numPattCurr = (n == 0) ? numPattTwoPrior : (n == 1) ? numPattOnePrior : 0;
for(int i = 2; i <= n; i++) { // finding F(n) up to the n given by the input
numPattCurr = numPattTwoPrior + numPattOnePrior; // at least this many times in F(n)
// adding to above all patterns found as part of concatenating F(n-1) and F(n-2), but not either on its own
middle:
for(int j = 1; j < pattLen; j++) { // starting at pos. 1 b/c [0, pattLen) is all F(n-1)
if(lastCharsInOnePrior.charAt(j) == 'E') {
continue;
}
StringBuilder compareWith = new StringBuilder(pattLen); // to compare with pattern
for(int k = 0; k < pattLen; k++) {
if(j + k >= pattLen) { // reached end of characters in F(n-1), start checking F(n-2)
int posInFirstChars = (j + k) % pattLen;
if(firstCharsInTwoPrior.charAt(posInFirstChars) == 'E') {
break middle; // none of the remaining overlap between F(n-1) and F(n-2) is as long as pattern, so can stop here
} else {
compareWith.append(firstCharsInTwoPrior.charAt(posInFirstChars));
}
} else {
compareWith.append(lastCharsInOnePrior.charAt(j + k));
}
}
if(pattern.equals(compareWith.toString())) {
numPattCurr++; // this overlap matched pattern
}
}
// changing characters of F(n-1) and F(n-2), as needed, for next iteration
StringBuilder[] updatedChars = updateChars(lastCharsInOnePrior, firstCharsInTwoPrior, lastCharsInTwoPrior, firstCharsInThreePrior);
lastCharsInTwoPrior = lastCharsInOnePrior;
firstCharsInThreePrior = firstCharsInTwoPrior;
lastCharsInOnePrior = updatedChars[0];
firstCharsInTwoPrior = updatedChars[1];
// changing number of times pattern found for F(n-1) and F(n-2) for next iteration
numPattTwoPrior = numPattOnePrior;
numPattOnePrior = numPattCurr;
}
System.out.println(numPattCurr);
System.exit(0);
}
}
我想我只留下了一行注释代码，当它是 else 块中的唯一一行时，它在所有测试用例中给出了完全相同的答案——尽管我用它替换它更正确。
关于我缺少什么或如何调试最后一个测试用例的任何建议？或者有兴趣与某人讨论，因为您正在为比赛做准备或只是在学习算法？请告诉我。