Merge pull request TheAlgorithms#1323 from prateekKrOraon/master

deadshotsb · web-flow · commit 03ee6f9579f7 · 2020-05-23T15:13:23.000+05:30
Addition of Rabin-Karp and String matching using Finite Automata
diff --git a/Others/RabinKarp.java b/Others/RabinKarp.java
@@ -0,0 +1,84 @@
+/**
+ * @author Prateek Kumar Oraon (https://github.com/prateekKrOraon)
+ */
+import java.util.Scanner;
+import java.lang.Math;
+
+//An implementation of Rabin-Karp string matching algorithm
+//Program will simply end if there is no match
+public class RabinKarp {
+
+    public static Scanner scanner = null;
+    public final static int d = 256;
+
+    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 pattern = scanner.nextLine();
+
+        int q = 101;
+        searchPat(text,pattern,q);
+
+    }
+
+    private static void searchPat(String text, String pattern, int q) {
+
+        int m = pattern.length();
+        int n = text.length();
+        int t = 0;
+        int p = 0;
+        int h = 1;
+        int j = 0;
+        int i =	0;
+
+        h = (int)Math.pow(d,m-1)%q;
+
+        for(i =0 ; i< m; i++){
+			//hash value is calculated for each character and then added with the hash value of the next character for pattern
+			// as well as the text for length equal to the length of pattern
+            p = (d*p + pattern.charAt(i))%q;
+            t = (d*t + text.charAt(i))%q;
+        }
+
+        for(i=0; i<=n-m;i++){
+			
+			//if the calculated hash value of the pattern and text matches then
+			//all the characters of the pattern is matched with the text of length equal to length of the pattern
+			//if all matches then pattern exist in string
+			//if not then the hash value of the first character of the text is subtracted and hash value of the next character after the end
+			//of the evaluated characters is added 
+            if(p==t){
+
+				//if hash value matches then the individual characters are matched
+                for(j=0;j<m;j++){
+                
+					//if not matched then break out of the loop
+					if(text.charAt(i+j) != pattern.charAt(j))
+						break;
+                }
+
+				//if all characters are matched then pattern exist in the string
+                if (j==m){
+                    System.out.println("Pattern found at index " + i);
+                }
+
+            }
+
+			//if i<n-m then hash value of the first character of the text is subtracted and hash value of the next character after the end
+			//of the evaluated characters is added to get the hash value of the next window of characters in the text
+            if ( i < n-m )
+            {
+                t = (d*(t - text.charAt(i)*h) + text.charAt(i+m))%q;
+
+				//if hash value becomes less than zero than q is added to make it positive
+                if (t < 0)
+                    t = (t + q);
+            }
+        }
+
+    }
+
+}
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;
+		
+	}
+	
+}
