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:
Collect a Java Stream to an Immutable Collection
Logout in an OAuth Secured Application
String Operations with Java Streams
Simple Single Sign-On with Spring Security OAuth2
Jackson Ignore Properties on Marshalling
Java Program to Perform LU Decomposition of any Matrix
Spring Security 5 – OAuth2 Login
Java Program to Implement Sorted Vector
Concatenating Strings In Java
Spring – Injecting Collections
Life Cycle of a Thread in Java
Converting String to Stream of chars
Java Program to Check if an UnDirected Graph is a Tree or Not Using DFS
Java Program to Apply Above-Below-on Test to Find the Position of a Point with respect to a Line
Guava – Join and Split Collections
Java Program to Generate Random Numbers Using Probability Distribution Function
Documenting a Spring REST API Using OpenAPI 3.0
How to Define a Spring Boot Filter?
Introduction to Thread Pools in Java
Giới thiệu Java 8
Java Program to implement Associate Array
Hướng dẫn Java Design Pattern – Iterator
Spring 5 and Servlet 4 – The PushBuilder
Servlet 3 Async Support with Spring MVC and Spring Security
Spring Cloud AWS – RDS
Spring MVC + Thymeleaf 3.0: New Features
OAuth2 for a Spring REST API – Handle the Refresh Token in Angular
Java Program to Perform Arithmetic Operations on Numbers of Size
Using JWT with Spring Security OAuth
Hướng dẫn Java Design Pattern – Factory Method
Java Program to Check if a Given Set of Three Points Lie on a Single Line or Not
Các kiểu dữ liệu trong java