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.

  1.  
  2. package com.sanfoundry.setandstring;
  3.  
  4. import java.util.Scanner;
  5.  
  6. public class SearchStringUsingDFA
  7. {
  8.     public static final int NO_OF_CHARS = 256;
  9.  
  10.     public static int getNextState(char[] pat, int M, int state, int x)
  11.     {
  12.         /*
  13.          * If the character c is same as next character in pattern,
  14.          * then simply increment state
  15.          */
  16.         if (state < M && x == pat[state])
  17.             return state + 1;
  18.         int ns, i;
  19.         /*
  20.          * ns stores the result which is next state
  21.          * ns finally contains the longest prefix which is also suffix
  22.          * in "pat[0..state-1]c"
  23.          * Start from the largest possible value and stop when you find
  24.          * a prefix which is also suffix
  25.          */
  26.         for (ns = state; ns > 0; ns--)
  27.         {
  28.             if (pat[ns - 1] == x)
  29.             {
  30.                 for (i = 0; i < ns - 1; i++)
  31.                 {
  32.                     if (pat[i] != pat[state - ns + 1 + i])
  33.                         break;
  34.                 }
  35.                 if (i == ns - 1)
  36.                     return ns;
  37.             }
  38.         }
  39.         return 0;
  40.     }
  41.  
  42.     /*
  43.      * This function builds the TF table which represents Finite Automata for a
  44.      * given pattern
  45.      */
  46.     public static void computeTF(char[] pat, int M, int[][] TF)
  47.     {
  48.         int state, x;
  49.         for (state = 0; state <= M; ++state)
  50.             for (x = 0; x < NO_OF_CHARS; ++x)
  51.                 TF[state][x] = getNextState(pat, M, state, x);
  52.     }
  53.  
  54.     /*
  55.      * Prints all occurrences of pat in txt
  56.      */
  57.     public static void search(char[] pat, char[] txt)
  58.     {
  59.         int M = pat.length;
  60.         int N = txt.length;
  61.         int[][] TF = new int[M + 1][NO_OF_CHARS];
  62.         computeTF(pat, M, TF);
  63.         // Process txt over FA.
  64.         int i, state = 0;
  65.         for (i = 0; i < N; i++)
  66.         {
  67.             state = TF[state][txt[i]];
  68.             if (state == M)
  69.             {
  70.                 System.out.print(pat);
  71.                 System.out.print(" found at " + (i - M + 1));
  72.             }
  73.         }
  74.     }
  75.  
  76.     public static void main(String[] args)
  77.     {
  78.         Scanner sc = new Scanner(System.in);
  79.         System.out.println("Enter the main string: ");
  80.         String main = sc.nextLine();
  81.         System.out.println("Enter the pattern string: ");
  82.         String pattern = sc.nextLine();
  83.         search(pattern.toCharArray(), main.toCharArray());
  84.         sc.close();
  85.     }
  86. }

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

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.