Skip to content

Create a new KMP Algorithm #3200

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 6 commits into from
Aug 3, 2022
Merged

Create a new KMP Algorithm #3200

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
6 commits
Select commit Hold shift + click to select a range
88f2eef
Create a new KMP Algorithm
MarcusCody Jul 30, 2022
c3b5df1
Merge branch 'master' into patch-1
MarcusCody Aug 3, 2022
f855fcc
Update KMPSearch.java
MarcusCody Aug 3, 2022
04060be
Create JUnit tests for KMP Search Algorithm
MarcusCody Aug 3, 2022
5191ef9
Update KMPSearch algorithm by removing the main
MarcusCody Aug 3, 2022
1cd4c8a
Added package
MarcusCody Aug 3, 2022
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
83 changes: 83 additions & 0 deletions src/main/java/com/thealgorithms/searches/KMPSearch.java
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -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.
66 changes: 66 additions & 0 deletions src/test/java/com/thealgorithms/searches/KMPSearchTest.java
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -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);

}
}