Consider the host string H and a sample pattern string P below. (a) Using the Na
ID: 3819492 • Letter: C
Question
Consider the host string H and a sample pattern string P below. (a) Using the Naive-String-Matcher, the (brute-force) string matching algorithm discussed in class, give all the pairs of characters from the host and pattern strings that are compared when finding the first occurrence of P in H. List the pairs in the order that the comparisons are made and in the form (P[i], H[j]), where/and j are zero-based indices, beginning with (P[0], H[0]). (b) Give 7r(P), the longest-prefix-proper-suffix array of P.] (c) Repeat exercise 3.(a) using the KMP-String-Matcher algorithm discussed in class. (d) Consider the alphabet E = {0, 1} and sigma*, the set of all bit strings. Also, consider the set of all (5, T) pairs, where 5 is a 4-bit substring of a 10-bit string T such that the brute-force string matching algorithm compares the most pairs of bits when finding the first occurrence of S in T. Of all such (S, T) pairs, give an example of 5 and T for which the KMP string matching algorithms compares the fewest pairs of bits when searching for the first occurrence of 5 in T. How many pairs of bits will each algorithm compare?Explanation / Answer
NOTE : Due to time constraint I was able to answer only first three. [And also as per the chegg policy I am entitled to answer only first full question]
public class PatternMatching {
/**
* Brute force algorithm to find the matching
*
* @param text
* @param pattern
*/
public void naiveAlgorithm(String text, String pattern) {
int M = pattern.length();
int N = text.length();
for (int i = 0; i <= N - M; i++) {
int j;
for (j = 0; j < M; j++) {
System.out.println(text.charAt(i + j) + ", "+pattern.charAt(j));
if (text.charAt(i + j) != pattern.charAt(j)) {
break;
}
}
if (j == M) {
System.out.println(" pattern found using naive algorithm, at position " + i);
return;
}
}
}
/**
* Computes the LPS array for the given pattern
* @param pattern
*/
public int[] getLPSArray(String pattern) {
int M = pattern.length();
int[] LPS = new int[M];
LPS[0] = 0;
int i = 1;
int j = 0;
while (i < M) {
if (pattern.charAt(i) == pattern.charAt(j)) {
j++;
LPS[i] = j;
i++;
} else {
if (j != 0) {
j = LPS[j - 1];
} else {
LPS[i] = j;
i++;
}
}
}
return LPS;
}
public void KMPSearch(String pattern, String text) {
int M = pattern.length();
int N = text.length();
int i = 0, j = 0;
int LPS[] = getLPSArray(pattern);
while (i < N) {
if (pattern.charAt(j) == text.charAt(i)) {
j++; i++;
}
if (j == M) {
System.out.println(" Pattern found using KMP algorithm, at position " + (i - j));
j = LPS[j - 1];
}
else if (i < N && pattern.charAt(j) != text.charAt(i)) {
if (j != 0) {
j = LPS[j - 1];
}
else {
i = i + 1;
}
}
}
}
public static void main(String args[]) {
String pattern = "0100122";
String text = "001201001001221";
PatternMatching pMatching = new PatternMatching();
/* 1. Using Naive Algorithm
*/
pMatching.naiveAlgorithm(text, pattern);
/* 2. Compute LPS Array
*/
System.out.print(" LPS Array for the given pattern is ");
int[] LPS = pMatching.getLPSArray(pattern);
for (int i=0; i<LPS.length; i++) {
System.out.print(LPS[i] +" ");
}
/* 3. Using KMP Algorithm
*/
pMatching.KMPSearch(pattern, text);
}
}
Output
0, 0
0, 1
0, 0
1, 1
2, 0
1, 0
2, 0
0, 0
1, 1
0, 0
0, 0
1, 1
0, 2
1, 0
0, 0
0, 1
0, 0
1, 1
0, 0
0, 0
1, 1
2, 2
2, 2
pattern found using naive algorithm, at position 7
LPS Array for the given pattern is 0 0 1 1 2 0 0
Pattern found using KMP algorithm, at index 7