Java Program to Perform Finite State Automaton based Search

This is a java program to perform search using DFA.

Here is the source code of the Java Program to Perform Finite State Automaton based Search. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

package com.maixuanviet.setandstring;
 
import java.util.Scanner;
 
public class SearchStringUsingDFA
{
    public static final int NO_OF_CHARS = 256;
 
    public static int getNextState(char[] pat, int M, int state, int x)
    {
        /*
         * If the character c is same as next character in pattern,
         * then simply increment state
         */
        if (state < M && x == pat[state])
            return state + 1;
        int ns, i;
        /*
         * ns stores the result which is next state
         * ns finally contains the longest prefix which is also suffix
         * in "pat[0..state-1]c"
         * Start from the largest possible value and stop when you find
         * a prefix which is also suffix
         */
        for (ns = state; ns > 0; ns--)
        {
            if (pat[ns - 1] == x)
            {
                for (i = 0; i < ns - 1; i++)
                {
                    if (pat[i] != pat[state - ns + 1 + i])
                        break;
                }
                if (i == ns - 1)
                    return ns;
            }
        }
        return 0;
    }
 
    /*
     * This function builds the TF table which represents Finite Automata for a
     * given pattern
     */
    public static void computeTF(char[] pat, int M, int[][] TF)
    {
        int state, x;
        for (state = 0; state <= M; ++state)
            for (x = 0; x < NO_OF_CHARS; ++x)
                TF[state][x] = getNextState(pat, M, state, x);
    }
 
    /*
     * Prints all occurrences of pat in txt
     */
    public static void search(char[] pat, char[] txt)
    {
        int M = pat.length;
        int N = txt.length;
        int[][] TF = new int[M + 1][NO_OF_CHARS];
        computeTF(pat, M, TF);
        // Process txt over FA.
        int i, state = 0;
        for (i = 0; i < N; i++)
        {
            state = TF[state][txt[i]];
            if (state == M)
            {
                System.out.print(pat);
                System.out.print(" found at " + (i - M + 1));
            }
        }
    }
 
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the main string: ");
        String main = sc.nextLine();
        System.out.println("Enter the pattern string: ");
        String pattern = sc.nextLine();
        search(pattern.toCharArray(), main.toCharArray());
        sc.close();
    }
}

Output:

$ javac SearchStringUsingDFA.java
$ java SearchStringUsingDFA
 
Enter the main string: 
Sanfoundry is No. 1 choice for Deep Hands-ON Trainings in SAN, Linux & C, Kernel & Device Driver Programming. Our Founder has trained employees of almost all Top Companies in India. Here are few of them: VMware, Citrix, Oracle, Motorola, Ericsson, Aricent, HP, Intuit, Microsoft, Cisco, SAP Labs, Siemens, Symantec, Redhat, Chelsio, Cavium Networks, ST Microelectronics, Samsung, LG-Soft, Wipro, TCS, HCL, IBM, Accenture, HSBC, Northwest Bank, Mphasis, Tata Elxsi, Tata Communications, Mindtree, Cognizant, mid size IT companies and many Startups. Students from top Universities and colleges such as NIT Trichy, BITS Pilani, University of California, Irvine, University of Texas, Austin & PESIT Bangalore have benefited a lot from these courses as well. The assignments and real time projects for our courses are of extremely high quality with excellent learning curve.
Enter the pattern string: 
Trainings
Trainings found at 45

Related posts:

Lấy ngày giờ hiện tại trong Java
Java Program to add two large numbers using Linked List
Java Program to Implement LinkedBlockingDeque API
Lớp lồng nhau trong java (Java inner class)
HttpClient 4 – Send Custom Cookie
Login For a Spring Web App – Error Handling and Localization
Concrete Class in Java
Java Program to Describe the Representation of Graph using Incidence Matrix
Returning Custom Status Codes from Spring Controllers
Java Program to Check Whether an Undirected Graph Contains a Eulerian Path
Spring Security Form Login
Java Program to implement Bit Matrix
Java Program to Implement Sieve Of Atkin
Guava – Join and Split Collections
Java Program to Implement Queue using Linked List
Java 8 Stream API Analogies in Kotlin
DistinctBy in the Java Stream API
Hướng dẫn Java Design Pattern – Dependency Injection
Converting Strings to Enums in Java
Intro to Inversion of Control and Dependency Injection with Spring
Refactoring Design Pattern với tính năng mới trong Java 8
Understanding Memory Leaks in Java
Rest Web service: Filter và Interceptor với Jersey 2.x (P1)
Java Program to do a Depth First Search/Traversal on a graph non-recursively
JPA/Hibernate Persistence Context
Java Program to Implement Merge Sort on n Numbers Without tail-recursion
Spring WebClient Filters
Implementing a Binary Tree in Java
Lớp Arrarys trong Java (Arrays Utility Class)
Adding Shutdown Hooks for JVM Applications
Filtering a Stream of Optionals in Java
Tổng quan về ngôn ngữ lập trình java