Java中最快的子串搜索方法？Kattis字符串匹配题超时求助

Hey there! I totally get the frustration when your code works correctly but hits a time limit on large inputs—been there, done that. Let's dive into how to speed up substring search in Java for this problem, since default approaches might not cut it for big datasets.

First, let's address the low-hanging fruit: input and output optimization. More often than not, timeouts happen not because your search logic is slow, but because you're reading/writing data inefficiently.

Input Optimization #

Ditch Scanner for BufferedReader—Scanner is convenient but notoriously slow for large inputs. Here's how to read your text and pattern efficiently:

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class StringMatcher {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String text = br.readLine();
        String pattern = br.readLine();
        br.close();
        
        // Your search logic here
    }
}

Output Optimization #

Instead of calling System.out.println() for every match (which flushes the buffer each time), collect all results in a StringBuilder and print them at once. This can save a ton of time for large numbers of matches:

StringBuilder sb = new StringBuilder();
for (int matchIndex : matches) {
    sb.append(matchIndex).append('\n');
}
System.out.print(sb);

Fast Substring Search Approaches #

Now, let's talk about the actual search algorithms.

1. Use Java's Built-in String.indexOf()

Don't underestimate the JDK's built-in methods—String.indexOf() is implemented with highly optimized native code (based on variations of the Boyer-Moore algorithm) that's often faster than hand-written implementations. Here's how to use it to find all matches:

int currentIndex = text.indexOf(pattern);
while (currentIndex != -1) {
    sb.append(currentIndex).append('\n');
    currentIndex = text.indexOf(pattern, currentIndex + 1);
}

This is usually the first thing to try because it's simple and leverages JDK optimizations you can't easily replicate.

2. Implement the KMP Algorithm

If the built-in method still isn't fast enough (unlikely, but possible for edge cases), the Knuth-Morris-Pratt (KMP) algorithm runs in O(n + m) time, where n is the text length and m is the pattern length. It avoids redundant comparisons by precomputing a "failure function" (partial match table).

Here's a clean Java implementation:

private static int[] computeFailureFunction(String pattern) {
    int m = pattern.length();
    int[] failure = new int[m];
    int j = 0;
    
    for (int i = 1; i < m; i++) {
        while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
            j = failure[j - 1];
        }
        if (pattern.charAt(i) == pattern.charAt(j)) {
            j++;
            failure[i] = j;
        } else {
            failure[i] = 0;
        }
    }
    return failure;
}

private static void kmpSearch(String text, String pattern, StringBuilder sb) {
    int n = text.length();
    int m = pattern.length();
    if (m == 0 || n < m) return;
    
    int[] failure = computeFailureFunction(pattern);
    int j = 0;
    
    for (int i = 0; i < n; i++) {
        while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
            j = failure[j - 1];
        }
        if (text.charAt(i) == pattern.charAt(j)) {
            j++;
            if (j == m) {
                sb.append(i - m + 1).append('\n');
                j = failure[j - 1];
            }
        }
    }
}

3. Implement the Boyer-Moore Algorithm

Boyer-Moore is often faster in practice than KMP because it skips more characters when a mismatch occurs (using "bad character" and "good suffix" heuristics). The bad character rule alone gives a huge speedup for most cases.

Here's an implementation focusing on the bad character rule:

import java.util.Arrays;

private static int[] buildBadCharTable(String pattern) {
    int[] badChar = new int[256]; // Assumes ASCII input (adjust if needed)
    Arrays.fill(badChar, -1);
    
    for (int i = 0; i < pattern.length(); i++) {
        badChar[pattern.charAt(i)] = i;
    }
    return badChar;
}

private static void boyerMooreSearch(String text, String pattern, StringBuilder sb) {
    int n = text.length();
    int m = pattern.length();
    if (m == 0 || n < m) return;
    
    int[] badChar = buildBadCharTable(pattern);
    int i = m - 1; // Current position in text
    int j = m - 1; // Current position in pattern
    
    while (i < n) {
        if (text.charAt(i) == pattern.charAt(j)) {
            if (j == 0) {
                sb.append(i).append('\n');
                i += m;
                j = m - 1;
            } else {
                i--;
                j--;
            }
        } else {
            int shift = j - badChar[text.charAt(i)];
            i += Math.max(shift, 1);
            j = m - 1;
        }
    }
}

Final Tips #

• Always start with the built-in indexOf() method—it's optimized for performance and will handle most cases.
• If you need to implement your own algorithm, Boyer-Moore is usually the best choice for real-world speed.
• Never overlook input/output optimization—this is the #1 cause of timeouts in Java for large datasets.

Give these approaches a try, and you should be able to beat the 2-second time limit on Kattis!

内容的提问来源于stack exchange，提问作者djharten