String Matching using Finite Automata added in Others/StringMatchFiniteAutomata.java

prateekKrOraon · prateekKrOraon · commit 36e30a011114 · 2020-05-22T03:53:05.000+05:30
diff --git a/Others/StringMatchFiniteAutomata.java b/Others/StringMatchFiniteAutomata.java
@@ -0,0 +1,91 @@
+/**
+ * @author Prateek Kumar Oraon (https://github.com/prateekKrOraon)
+ */
+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;
+		
+	}
+	
+}
