Repository: TheAlgorithms/Java
Pull request #5222 (2024-06-12 13:15:00)

refactor: redesign `StringMatchFiniteAutomata`

Related to #5164

- [X] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [X] This pull request is all my own work -- I have not plagiarized it.
- [X] All filenames are in PascalCase.
- [X] All functions and variable names follow Java naming conventions.
- [X] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
- [X] All new code is formatted with `clang-format -i --style=file path/to/your/file.java`

codecov-commenter: ## [Codecov](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5222?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) Report
Attention: Patch coverage is `74.07407%` with `7 lines` in your changes missing coverage. Please review.
> Project coverage is 38.89%. Comparing base [(`3ecd135`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/3ecd13508a8ebe533afe3486bac66cb3ab54cecb?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`9505edb`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/9505edbe1ada966e066fb34197f8f5fdd3e87792?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).

| [Files](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5222?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) | Patch % | Lines |
|---|---|---|
| [...healgorithms/others/StringMatchFiniteAutomata.java](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5222?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Fcom%2Fthealgorithms%2Fothers%2FStringMatchFiniteAutomata.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms#diff-c3JjL21haW4vamF2YS9jb20vdGhlYWxnb3JpdGhtcy9vdGhlcnMvU3RyaW5nTWF0Y2hGaW5pdGVBdXRvbWF0YS5qYXZh) | 74.07% | [7 Missing :warning: ](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5222?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) |

<details><summary>Additional details and impacted files</summary>


```diff
@@             Coverage Diff              @@
##             master    #5222      +/-   ##
============================================
+ Coverage     38.72%   38.89%   +0.17%     
- Complexity     2383     2398      +15     
============================================
  Files           517      517              
  Lines         15392    15394       +2     
  Branches       2954     2954              
============================================
+ Hits           5961     5988      +27     
+ Misses         9144     9119      -25     
  Partials        287      287              
```



</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5222?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).

vil02: Let's focus on #5221 first.

Patch:
diff --git a/src/main/java/com/thealgorithms/others/StringMatchFiniteAutomata.java b/src/main/java/com/thealgorithms/others/StringMatchFiniteAutomata.java
index 22979e59..561845f4 100644
--- a/src/main/java/com/thealgorithms/others/StringMatchFiniteAutomata.java
+++ b/src/main/java/com/thealgorithms/others/StringMatchFiniteAutomata.java
@@ -1,80 +1,125 @@
 package com.thealgorithms.others;
 
+import java.util.Set;
+import java.util.TreeSet;
+
 /**
- * @author Prateek Kumar Oraon (https://github.com/prateekKrOraon)
+ * A class to perform string matching using <a href="https://en.wikipedia.org/wiki/Finite-state_machine">finite automata</a>.
+ *
+ * @author <a href="https://github.com/prateekKrOraon">Prateek Kumar Oraon</a>
  */
-import java.util.Scanner;
-
-// An implementation of string matching using finite automata
 public final class StringMatchFiniteAutomata {
-    private StringMatchFiniteAutomata() {
-    }
-
-    public static final int CHARS = 256;
-    public static int[][] fa;
-    public static Scanner scanner = null;
-
-    public static void main(String[] args) {
-        scanner = new Scanner(System.in);
-        System.out.println("Enter String");
-        String text = scanner.nextLine();
-        System.out.println("Enter pattern");
-        String pat = scanner.nextLine();
 
-        searchPat(text, pat);
+    // Constants
+    private static final int CHARS = Character.MAX_VALUE + 1; // Total number of characters in the input alphabet
 
-        scanner.close();
+    // Private constructor to prevent instantiation
+    private StringMatchFiniteAutomata() {
     }
 
-    public static void searchPat(String text, String pat) {
-        int m = pat.length();
-        int n = text.length();
-
-        fa = new int[m + 1][CHARS];
-
-        computeFA(pat, m, fa);
-
-        int state = 0;
-        for (int i = 0; i < n; i++) {
-            state = fa[state][text.charAt(i)];
-
-            if (state == m) {
-                System.out.println("Pattern found at index " + (i - m + 1));
+    /**
+     * Searches for the pattern in the given text using finite automata.
+     *
+     * @param text    The text to search within.
+     * @param pattern The pattern to search for.
+     */
+    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;
     }
 
-    // Computes finite automata for the pattern
-    public static void computeFA(String pat, int m, int[][] fa) {
-        for (int state = 0; state <= m; ++state) {
+    /**
+     * 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) {
-                fa[state][x] = getNextState(pat, m, state, x);
+                stateTransitionTable[state][x] = getNextState(pattern, patternLength, state, x);
             }
         }
+
+        return stateTransitionTable;
     }
 
-    public static int getNextState(String pat, int m, int state, int x) {
-        // if current state is less than length of pattern
-        // and input character of pattern matches the character in the alphabet
-        // then automata goes to next state
-        if (state < m && x == pat.charAt(state)) {
+    /**
+     * 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 (pat.charAt(ns - 1) == x) {
+            if (pattern.charAt(ns - 1) == x) {
+                boolean match = true;
                 for (int i = 0; i < ns - 1; i++) {
-                    if (pat.charAt(i) != pat.charAt(state - ns + i + 1)) {
+                    if (pattern.charAt(i) != pattern.charAt(state - ns + i + 1)) {
+                        match = false;
                         break;
                     }
-
-                    if (i == ns - 1) {
-                        return ns;
-                    }
+                }
+                if (match) {
+                    return ns;
                 }
             }
         }
 
+        // If no prefix which is also a suffix is found, return 0
         return 0;
     }
+
+    /**
+     * A class representing the finite automata for pattern matching.
+     */
+    private static final class FiniteAutomata {
+        private int state = 0;
+        private final int[][] stateTransitionTable;
+
+        private FiniteAutomata(int[][] stateTransitionTable) {
+            this.stateTransitionTable = stateTransitionTable;
+        }
+
+        /**
+         * Consumes an input character and transitions to the next state.
+         *
+         * @param input The input character.
+         */
+        private void consume(final char input) {
+            state = stateTransitionTable[state][input];
+        }
+
+        /**
+         * Gets the current state of the finite automata.
+         *
+         * @return The current state.
+         */
+        private int getState() {
+            return state;
+        }
+    }
 }


Test patch:
diff --git a/src/test/java/com/thealgorithms/others/StringMatchFiniteAutomataTest.java b/src/test/java/com/thealgorithms/others/StringMatchFiniteAutomataTest.java
new file mode 100644
index 00000000..6e1947b7
--- /dev/null
+++ b/src/test/java/com/thealgorithms/others/StringMatchFiniteAutomataTest.java
@@ -0,0 +1,23 @@
+package com.thealgorithms.others;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+import java.util.Set;
+import java.util.stream.Stream;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.Arguments;
+import org.junit.jupiter.params.provider.MethodSource;
+
+class StringMatchFiniteAutomataTest {
+
+    @ParameterizedTest
+    @MethodSource("provideTestCases")
+    void searchPattern(String text, String pattern, Set<Integer> expectedOutput) {
+        assertEquals(expectedOutput, StringMatchFiniteAutomata.searchPattern(text, pattern));
+    }
+
+    private static Stream<Arguments> provideTestCases() {
+        return Stream.of(Arguments.of("abcbcabc", "abc", Set.of(0, 5)), Arguments.of("", "abc", Set.of()), Arguments.of("", "", Set.of()), Arguments.of("a", "b", Set.of()), Arguments.of("a", "a", Set.of(0)), Arguments.of("abcdabcabcabcd", "abcd", Set.of(0, 10)), Arguments.of("abc", "bcd", Set.of()),
+            Arguments.of("abcdefg", "xyz", Set.of()), Arguments.of("abcde", "", Set.of(1, 2, 3, 4, 5)), Arguments.of("abcabcabc", "abc", Set.of(0, 3, 6)), Arguments.of("abcabcabc", "abcabcabc", Set.of(0)), Arguments.of("aaabbbaaa", "aaa", Set.of(0, 6)), Arguments.of("abcdefg", "efg", Set.of(4)));
+    }
+}