forked from dimpeshmalviya/JavaBasicPrograms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathKMPAlgorithm.java
More file actions
29 lines (26 loc) · 777 Bytes
/
KMPAlgorithm.java
File metadata and controls
29 lines (26 loc) · 777 Bytes
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
class GfG {
public static ArrayList<Integer> computeLPSArray(String pattern) {
int n = pattern.length();
ArrayList<Integer> lps = new ArrayList<>();
for (int k = 0; k < n; k++) lps.add(0);
// length of the previous longest prefix suffix
int len = 0;
int i = 1;
while (i < n) {
if (pattern.charAt(i) == pattern.charAt(len)) {
len++;
lps.set(i, len);
i++;
} else {
if (len != 0) {
// fall back in the pattern
len = lps.get(len - 1);
} else {
lps.set(i, 0);
i++;
}
}
}
return lps;
}
}