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:
How to Get the Last Element of a Stream in Java?
Jackson – Marshall String to JsonNode
REST Web service: HTTP Status Code và xử lý ngoại lệ RESTful web service với Jersey 2.x
Lập trình mạng với java
Guide to java.util.Formatter
Registration with Spring Security – Password Encoding
REST Web service: Tạo ứng dụng Java RESTful Client với Jersey Client 2.x
Java Program to Implement Traveling Salesman Problem using Nearest neighbour Algorithm
Java Program to Implement Circular Doubly Linked List
Servlet 3 Async Support with Spring MVC and Spring Security
New Features in Java 11
StringBuilder vs StringBuffer in Java
Java Program to Check if a Given Graph Contain Hamiltonian Cycle or Not
Spring Boot Security Auto-Configuration
Java Program to Perform Naive String Matching
Java Program to Implement D-ary-Heap
Java Program to Implement Triply Linked List
Working with Kotlin and JPA
Removing all duplicates from a List in Java
How to Use if/else Logic in Java 8 Streams
Spring Boot: Customize the Jackson ObjectMapper
Spring Boot - Apache Kafka
Làm thế nào tạo instance của một class mà không gọi từ khóa new?
Java Program to Check whether Graph is a Bipartite using 2 Color Algorithm
The Guide to RestTemplate
Quick Guide on Loading Initial Data with Spring Boot
Java Program to Find the Number of Ways to Write a Number as the Sum of Numbers Smaller than Itself
Hướng dẫn Java Design Pattern – Abstract Factory
Apache Camel with Spring Boot
How to Replace Many if Statements in Java
Hướng dẫn Java Design Pattern – Prototype
Java Program to Implement Brent Cycle Algorithm