JAVA:实现使用finite automata实现字符串匹配算法(附完整源码)

package com.thealgorithms.others;

import java.util.Scanner;

// An implementaion of string matching using finite automata
public class 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);

        scanner.close();
    }

    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));
            }
        }
    }

    // Computes finite automata for the partern
    public static void computeFA(String pat, int m, int[][] FA) {

        for (int state = 0; state <= m; ++state) {
            for (int x = 0; x < CHARS; ++x) {
                FA[state][x] = getNextState(pat, m, state, x);
            }
        }
    }

    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)) {
            return state + 1;
        }

        for (int ns = state; ns > 0; ns--) {

            if (pat.charAt(ns - 1) == x) {

                for (int i = 0; i < ns - 1; i++) {

                    if (pat.charAt(i) != pat.charAt(state - ns + i + 1)) {
                        break;
                    }

                    if (i == ns - 1) {
                        return ns;
                    }
                }
            }
        }

        return 0;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83