BOJ. Find (1786)

BOJ 1786: Find · 한국어 · 日本語

Given a text T and a non-empty pattern P, find every occurrence of P in T. KMP avoids rescanning text characters after a mismatch. The problem guarantees that P is non-empty; the search function below also returns no matches for an empty pattern without indexing into it.

Prefix function and search

pi[i] is the length of the longest proper prefix of P[0..i] that is also a suffix. While building the prefix function, a mismatch shortens the candidate prefix with pi[j - 1]; a match extends it.

During search, j is the number of pattern characters currently matched. On a mismatch, fall back to pi[j - 1] and continue matching. When j == P.length(), the match ends at text index i, so its starting position is i - P.length() + 2: this converts the zero-based index to the 1-based position required by the problem. Immediately fall back to j = pi[j - 1] after recording a match. That retains a possible overlap between the matched suffix and the next prefix, so overlapping occurrences are all reported in ascending order.

The prefix-function construction and search together take O(|T| + |P|) time. Additional space is O(|P| + K) for the prefix array and the list of K matches.

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        String text = input.readLine();
        String pattern = input.readLine();

        List<Integer> positions = findMatches(text, pattern);
        StringBuilder output = new StringBuilder();
        output.append(positions.size()).append('\n');
        for (int i = 0; i < positions.size(); i++) {
            if (i > 0) output.append(' ');
            output.append(positions.get(i));
        }
        System.out.print(output);
    }

    private static List<Integer> findMatches(String text, String pattern) {
        List<Integer> positions = new ArrayList<>();
        if (pattern.isEmpty()) return positions;

        int[] pi = prefixFunction(pattern);
        int matched = 0;
        for (int i = 0; i < text.length(); i++) {
            while (matched > 0 && text.charAt(i) != pattern.charAt(matched)) {
                matched = pi[matched - 1];
            }
            if (text.charAt(i) == pattern.charAt(matched)) {
                matched++;
                if (matched == pattern.length()) {
                    positions.add(i - pattern.length() + 2);
                    matched = pi[matched - 1];
                }
            }
        }
        return positions;
    }

    private static int[] prefixFunction(String pattern) {
        int[] pi = new int[pattern.length()];
        int matched = 0;
        for (int i = 1; i < pattern.length(); i++) {
            while (matched > 0 && pattern.charAt(i) != pattern.charAt(matched)) {
                matched = pi[matched - 1];
            }
            if (pattern.charAt(i) == pattern.charAt(matched)) {
                pi[i] = ++matched;
            }
        }
        return pi;
    }
}