Here are some tips for finding solutions to java problems about “kmp java” Code Answer’s. We are going to list out some java programming problem, you can find the solution for your programming question if you get stuck in coding. Getting stuck in programming is quite normal for all the developers. Most of the beginners and even experienced programmers take help from some resources but that doesn’t mean they are dumb or bad programmers. Below are some solution about “kmp java” Code Answer’s.
kmp java
xxxxxxxxxx
1
static int KMPSearch(String pat, String txt) {
2
ArrayList<Integer> matchAtIndexs = new ArrayList<>();
3
int M = pat.length();
4
int N = txt.length();
5
int lps[] = new int[M];
6
int j = 0;
7
computeLPSArray(pat, M, lps);
8
int i = 0;
9
while (i < N) {
10
if (pat.charAt(j) == txt.charAt(i)) {
11
j++;
12
i++;
13
}
14
if (j == M) {
15
matchAtIndexs.add(i - j);
16
j = lps[j - 1];
17
} else if (i < N && pat.charAt(j) != txt.charAt(i)) {
18
if (j != 0)
19
j = lps[j - 1];
20
else
21
i = i + 1;
22
}
23
}
24
return matchAtIndexs.size();
25
}
26
27
static void computeLPSArray(String pat, int M, int lps[]) {
28
int len = 0;
29
int i = 1;
30
lps[0] = 0;
31
while (i < M) {
32
if (pat.charAt(i) == pat.charAt(len)) {
33
len++;
34
lps[i] = len;
35
i++;
36
} else {
37
if (len != 0) {
38
len = lps[len - 1];
39
40
} else {
41
lps[i] = len;
42
i++;
43
}
44
}
45
}
46
}
47
xxxxxxxxxx
1
ArrayList<Integer> matachedAtindex;
2
3
void KMPSearch(char[] pat, char[] txt) {
4
int m = pat.length;
5
int n = txt.length;
6
int j = 0;
7
int i = 0;
8
matachedAtindex = new ArrayList<>();
9
lpsCompute(pat);
10
while (i < n) {
11
if (pat[j] == txt[i]) {
12
j++;
13
i++;
14
}
15
if (j == m) {
16
matachedAtindex.add((i - j));
17
j = lps[j - 1];
18
} else if (i < n && pat[j] != txt[i]) {
19
if (j != 0)
20
j = lps[j - 1];
21
else
22
i = i + 1;
23
}
24
}
25
}
26
27
static int lps[];
28
29
static void lpsCompute(char[] pat) {
30
int n = pat.length;
31
lps = new int[n];
32
int j = 0;
33
int i = 1;
34
while (i < n) {
35
if (pat[i] == pat[j]) {
36
j++;
37
lps[i] = j;
38
i++;
39
} else {
40
if (j != 0) {
41
j = lps[j - 1];
42
} else {
43
lps[i] = j;
44
i++;
45
}
46
}
47
}
48
}
49