Repository: TheAlgorithms/Java
Pull request #3200 (2022-07-30 16:43:04)

Create a new KMP Algorithm
An important issue in computer science is pattern searching. Pattern searching methods display the search results when we do a string search in a database, browser, or notepad/word file.

### **Describe your change:**

- [x] Add an algorithm?
- [ ] Fix a bug or typo in an existing algorithm?
- [ ] Documentation change?

#### References

[Knuth–Morris–Pratt algorithm](https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm)

### **Checklist:**


- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] I know that pull requests will not be merged if they fail the automated tests.
- [x] This PR only changes one algorithm file. To ease review, please open separate PRs for separate algorithms.
- [x] All new Java files are placed inside an existing directory.
- [x] All filenames are in all uppercase characters with no spaces or dashes.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in its comments that points to Wikipedia or other similar explanation.


MarcusCody: I have added the test case for KMPSearch Algorithm 

Patch:
diff --git a/src/main/java/com/thealgorithms/searches/KMPSearch.java b/src/main/java/com/thealgorithms/searches/KMPSearch.java
new file mode 100644
index 00000000..0f3239ce
--- /dev/null
+++ 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.


Test patch:
diff --git a/src/test/java/com/thealgorithms/searches/KMPSearchTest.java b/src/test/java/com/thealgorithms/searches/KMPSearchTest.java
new file mode 100644
index 00000000..a5a396a9
--- /dev/null
+++ 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);
+    	
+    }
+}