-
Notifications
You must be signed in to change notification settings - Fork 49
Expand file tree
/
Copy pathKMPAlgorithm.java
More file actions
95 lines (78 loc) · 2.99 KB
/
KMPAlgorithm.java
File metadata and controls
95 lines (78 loc) · 2.99 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
// KMP Algorithm in Java
// ------------------------------------------------------
// Author: Jatin Vishwakarma
// Description: Implementation of the Knuth–Morris–Pratt (KMP)
// Pattern Searching Algorithm in Java.
// This algorithm efficiently finds all occurrences of a pattern
// in a given text with O(n + m) time complexity.
import java.util.Scanner;
public class KMPAlgorithm {
// Function to preprocess the pattern and build the LPS (Longest Prefix Suffix) array
private static void computeLPSArray(String pattern, int[] lps) {
int length = 0; // length of the previous longest prefix suffix
int i = 1;
lps[0] = 0; // LPS of the first character is always 0
// Loop to calculate lps[i] for i = 1 to pattern.length - 1
while (i < pattern.length()) {
if (pattern.charAt(i) == pattern.charAt(length)) {
length++;
lps[i] = length;
i++;
} else {
if (length != 0) {
// This is tricky — consider the example "AAACAAAA"
length = lps[length - 1];
} else {
lps[i] = 0;
i++;
}
}
}
}
// KMP Search Function
public static void KMPSearch(String pattern, String text) {
int M = pattern.length();
int N = text.length();
// Create LPS array
int[] lps = new int[M];
computeLPSArray(pattern, lps);
int i = 0; // index for text[]
int j = 0; // index for pattern[]
boolean found = false;
while (i < N) {
if (pattern.charAt(j) == text.charAt(i)) {
i++;
j++;
}
if (j == M) {
System.out.println("✅ Pattern found at index: " + (i - j));
j = lps[j - 1];
found = true;
}
// Mismatch after j matches
else if (i < N && pattern.charAt(j) != text.charAt(i)) {
// Do not match lps[0..lps[j-1]] characters, they will match anyway
if (j != 0)
j = lps[j - 1];
else
i++;
}
}
if (!found)
System.out.println("❌ Pattern not found in the given text.");
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("=====================================");
System.out.println(" KMP STRING MATCHING ALGORITHM");
System.out.println("=====================================");
System.out.print("Enter the text: ");
String text = sc.nextLine();
System.out.print("Enter the pattern to search: ");
String pattern = sc.nextLine();
System.out.println("\n🔍 Searching for pattern...");
KMPSearch(pattern, text);
System.out.println("\n--- Program Completed Successfully ---");
sc.close();
}
}