3. Create a class called W3Q3.java and copy the search algorithms you implemente
ID: 3554428 • Letter: 3
Question
3. Create a class called W3Q3.java and copy the search algorithms you
implemented in Q1 and Q2. Instrument your search algorithms (add code) to
counting the number of comparisons that take place and to print this value to
the console when each algorithm terminates.
Implement a main method that performs the tests carried out in Q1 and Q2 and
compare the number of comparisons. Add a comment at the top of the class
that identifies, for each test, which algorithm took the least number of
comparisons.
HINT: the comment should look something like this:
/**
* This is my answer
Explanation / Answer
public class KMPplus {
private String pattern;
private int[] next;
// create Knuth-Morris-Pratt NFA from pattern
public KMPplus(String pattern)
{
this.pattern = pattern;
int M = pattern.length();
next = new int[M];
int j = -1;
for (int i = 0; i < M; i++) {
if (i == 0)
next[i] = -1;
else if (pattern.charAt(i) != pattern.charAt(j)) next[i] = j;
else
next[i] = next[j];
while (j >= 0 && pattern.charAt(i) != pattern.charAt(j))
{
j = next[j];
}
j++;
}
for (int i = 0; i < M; i++)
StdOut.println("next[" + i + "] = " + next[i]);
}
// return offset of first occurrence of text in pattern (or N if no match)
// simulate the NFA to find match
public int search(String text)
{
int M = pattern.length();
int N = text.length();
int i, j;
for (i = 0, j = 0; i < N && j < M; i++) {
while (j >= 0 && text.charAt(i) != pattern.charAt(j))
j = next[j];
j++;
}
if (j == M) return i - M;
return N;
}
// test client
public static void main(String[] args) {
String pattern = args[0];
String text = args[1];
int M = pattern.length();
int N = text.length();
// substring search
KMPplus kmp = new KMPplus(pattern);
int offset = kmp.search(text);
// print results
StdOut.println("text: " + text);
StdOut.print("pattern: ");
for (int i = 0; i < offset; i++)
StdOut.print(" ");
StdOut.println(pattern);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.