Repository: TheAlgorithms/Java
File: src/main/java/com/thealgorithms/others/StringMatchFiniteAutomata.java (Java)

Code before:
     * @param text    The text to search within.
     * @param pattern The pattern to search for.
     */
    public static Set<Integer> searchPattern(String text, String pattern) {
        Set<Integer> indexFound = new TreeSet<>();
        int patternLength = pattern.length();
        int textLength = text.length();

        // Initialize finite automata table
        finiteAutomata = new int[patternLength + 1][CHARS];

        // Preprocess the pattern to create the finite automata table
        computeFiniteAutomata(pattern, patternLength);

        int state = 0; // Initial state

        // Process the text over the finite automata
        for (int i = 0; i < textLength; i++) {
            state = finiteAutomata[state][text.charAt(i)];

            if (state == patternLength) {
                indexFound.add(i - patternLength + 1);
            }
        }
        return indexFound;
    }

    /**
     * Computes the finite automata table for the given pattern.
     *
     * @param pattern       The pattern to preprocess.
     * @param patternLength The length of the pattern.
     */
    private static void computeFiniteAutomata(String pattern, int patternLength) {
        for (int state = 0; state <= patternLength; ++state) {
            for (int x = 0; x < CHARS; ++x) {
                finiteAutomata[state][x] = getNextState(pattern, patternLength, state, x);
            }
        }
    }

    /**
     * Gets the next state for the finite automata.
     *
     * @param pattern       The pattern being matched.
     * @param patternLength The length of the pattern.
     * @param state         The current state.
     * @param x             The current character from the input alphabet.
     * @return The next state.
     */
    private static int getNextState(String pattern, int patternLength, int state, int x) {

Review comment (suggestion):
I think that this method should look somehow like that:
```java
public static Set<Integer> searchPattern(final String text, final String pattern) {
    final var stateTransitionTable = computeStateTransitionTable(pattern);
    FiniteAutomata finiteAutomata = new FiniteAutomata(stateTransitionTable);

    Set<Integer> indexFound = new TreeSet<>();
    for (int i = 0; i < text.length(); i++) {
        finiteAutomata.consume(text.charAt(i));

        if (finiteAutomata.getState() == pattern.length()) {
            indexFound.add(i - pattern.length() + 1);
        }
    }
    return indexFound;
}
```
The `FiniteAutomata` is a class with two `private` fields: `state` and `stateTransitionTable`. The method
`public consume(final char input)` updates the `state` according to `stateTransitionTable`.

Code after:
     * Computes the finite automata table for the given pattern.
     *
     * @param pattern The pattern to preprocess.
     * @return The state transition table.
     */
    private static int[][] computeStateTransitionTable(final String pattern) {
        final int patternLength = pattern.length();
        int[][] stateTransitionTable = new int[patternLength + 1][CHARS];

        for (int state = 0; state <= patternLength; ++state) {
            for (int x = 0; x < CHARS; ++x) {
                stateTransitionTable[state][x] = getNextState(pattern, patternLength, state, x);
            }
        }

        return stateTransitionTable;
    }

    /**
     * Gets the next state for the finite automata.
     *
     * @param pattern       The pattern being matched.
     * @param patternLength The length of the pattern.
     * @param state         The current state.
     * @param x             The current character from the input alphabet.
     * @return The next state.
     */
    private static int getNextState(final String pattern, final int patternLength, final int state, final int x) {
        // If the current state is less than the length of the pattern
        // and the character matches the pattern character, go to the next state
        if (state < patternLength && x == pattern.charAt(state)) {
            return state + 1;
        }

        // Check for the highest prefix which is also a suffix
        for (int ns = state; ns > 0; ns--) {
            if (pattern.charAt(ns - 1) == x) {
                boolean match = true;
                for (int i = 0; i < ns - 1; i++) {
                    if (pattern.charAt(i) != pattern.charAt(state - ns + i + 1)) {
                        match = false;
                        break;
                    }
                }
                if (match) {
                    return ns;
                }
            }
        }

        // If no prefix which is also a suffix is found, return 0