Add KMP String Search Algorithm (#3200)

MarcusCody · web-flow · commit 965c20381cd2 · 2022-08-03T20:46:44.000+03:00
diff --git a/src/main/java/com/thealgorithms/searches/KMPSearch.java b/src/main/java/com/thealgorithms/searches/KMPSearch.java
@@ -0,0 +1,83 @@
+package com.thealgorithms.searches;
+
+class KMPSearch {
+    int KMPSearch(String pat, String txt)
+    {
+        int M = pat.length();
+        int N = txt.length();
+ 
+        // create lps[] that will hold the longest
+        // prefix suffix values for pattern
+        int lps[] = new int[M];
+        int j = 0; // index for pat[]
+ 
+        // Preprocess the pattern (calculate lps[]
+        // array)
+        computeLPSArray(pat, M, lps);
+ 
+        int i = 0; // index for txt[]
+        while ((N - i) >= (M - j)) {
+            if (pat.charAt(j) == txt.charAt(i)) {
+                j++;
+                i++;
+            }
+            if (j == M) {
+                System.out.println("Found pattern "
+                                + "at index " + (i - j));
+                int index = (i - j);
+                j = lps[j - 1];
+                return index;
+        
+            }
+ 
+            // mismatch after j matches
+            else if (i < N && pat.charAt(j) != txt.charAt(i)) {
+                // Do not match lps[0..lps[j-1]] characters,
+                // they will match anyway
+                if (j != 0)
+                    j = lps[j - 1];
+                else
+                    i = i + 1;
+            }
+        }
+        System.out.println("No pattern found");
+		return -1;
+    }
+ 
+    void computeLPSArray(String pat, int M, int lps[])
+    {
+        // length of the previous longest prefix suffix
+        int len = 0;
+        int i = 1;
+        lps[0] = 0; // lps[0] is always 0
+ 
+        // the loop calculates lps[i] for i = 1 to M-1
+        while (i < M) {
+            if (pat.charAt(i) == pat.charAt(len)) {
+                len++;
+                lps[i] = len;
+                i++;
+            }
+            else // (pat[i] != pat[len])
+            {
+                // This is tricky. Consider the example.
+                // AAACAAAA and i = 7. The idea is similar
+                // to search step.
+                if (len != 0) {
+                    len = lps[len - 1];
+ 
+                    // Also, note that we do not increment
+                    // i here
+                }
+                else // if (len == 0)
+                {
+                    lps[i] = len;
+                    i++;
+                }
+            }
+        }
+    }
+ 
+
+}
+// This code has been contributed by Amit Khandelwal.
diff --git a/src/test/java/com/thealgorithms/searches/KMPSearchTest.java b/src/test/java/com/thealgorithms/searches/KMPSearchTest.java
@@ -0,0 +1,66 @@
+
+package com.thealgorithms.searches;
+
+import org.junit.jupiter.api.Test;
+import static org.junit.jupiter.api.Assertions.*;
+
+class KMPSearchTest {
+    
+    @Test
+    // valid test case
+    public void KMPSearchTestLast() {
+    	String txt = "ABABDABACDABABCABAB";
+        String pat = "ABABCABAB";
+        KMPSearch kmpSearch = new KMPSearch();
+        int value = kmpSearch.KMPSearch(pat, txt);
+        System.out.println(value);
+        assertEquals(value, 10);
+    	
+    }
+    
+    @Test
+    // valid test case
+    public void KMPSearchTestFront() {
+    	String txt = "AAAAABAAABA";
+    	String pat = "AAAA";
+        KMPSearch kmpSearch = new KMPSearch();
+        int value = kmpSearch.KMPSearch(pat, txt);
+        System.out.println(value);
+        assertEquals(value, 0);
+    	
+    }
+    
+    @Test
+    // valid test case
+    public void KMPSearchTestMiddle() {
+    	String txt = "AAACAAAAAC";
+    	String pat = "AAAA";
+        KMPSearch kmpSearch = new KMPSearch();
+        int value = kmpSearch.KMPSearch(pat, txt);
+        System.out.println(value);
+        assertEquals(value, 4);
+    	
+    }
+    @Test
+    // valid test case
+    public void KMPSearchTestNotFound() {
+    	String txt = "AAABAAAA";
+    	String pat = "AAAA";
+        KMPSearch kmpSearch = new KMPSearch();
+        int value = kmpSearch.KMPSearch(pat, txt);
+        System.out.println(value);
+        assertEquals(value, 4);
+    	
+    }
+    @Test
+    // not valid test case
+    public void KMPSearchTest4() {
+    	String txt = "AABAAA";
+    	String pat = "AAAA";
+        KMPSearch kmpSearch = new KMPSearch();
+        int value = kmpSearch.KMPSearch(pat, txt);
+        System.out.println(value);
+        assertEquals(value, -1);
+    	
+    }
+}
