-
Notifications
You must be signed in to change notification settings - Fork 0
/
KMP Algorithm
46 lines (44 loc) · 1.07 KB
/
KMP Algorithm
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
public class Solution {
public static boolean findPattern(String p, String s) {
int n = p.length();
int m = s.length();
int[] lps = new int[n];
computeLPSArray(p,s,lps);
int i = 0;
int j = 0;
while(i<m){
if(s.charAt(i)==p.charAt(j)){
j++;
i++;
}
else{
if(j!=0)
j = lps[j-1];
else
i++;
}
if(j==n)
return true;
}
return false;
}
public static void computeLPSArray(String p, String s, int[] lps){
int len = 0;
int i = 1;
while(i<p.length()){
if(p.charAt(i)==p.charAt(len)){
lps[i] = len + 1;
len++;
i++;
}
else {
if(len!=0)
len = lps[len-1];
else{
lps[i] = 0;
i++;
}
}
}
}
}