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

Changes from 1 commit
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
Next Next commit
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.
  • Loading branch information
@MarcusCody
MarcusCody authored Jul 30, 2022
commit 88f2eefffcd2ec422154ec2b4769cf515a571f5d
84 changes: 84 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,84 @@
package com.thealgorithms.searches;

class KMPSerach {
void 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));
j = lps[j - 1];
}

// 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;
}
}
}

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++;
}
}
}
}

// Driver program to test above function
public static void main(String args[])
{
String txt = "ABABDABACDABABCABAB";
String pat = "ABABCABAB";
new KMPSerach().KMPSearch(pat, txt);
}
}
// This code has been contributed by Amit Khandelwal.