Question: public static int brute _ force ( String text, String pattern ) { int n = text.length ( ) ; int m = pattern.length (

public static int brute_force(String text, String pattern){
int n = text.length();
int m = pattern.length();
for (int i =0; i <= n - m; i++){
int j =0;
while (j < m && pattern.charAt(j)== text.charAt(i + j)){
j++;
}
if (j == m){
return i;
}
}
return -1;
}
public static int[] shift_table(String pattern){
int m = pattern.length();
int[] table = new int[256]; // Assuming ASCII characters
Arrays.fill(table, m);
for (int i =0; i < m -1; i++){
table[pattern.charAt(i)]= m -1- i;
}
return table;
}
public static int horspool(String text, String pattern){
int n = text.length();
int m = pattern.length();
int[] table = shift_table(pattern);
int i = m -1;
while (i < n){
int k =0;
while (k < m && pattern.charAt(m -1- k)== text.charAt(i - k)){
k++;
}
if (k == m){
return i - m +1;
} else {
i += table[text.charAt(i)];
}
}
return -1;
}
public static void main(String[] args){
String text = "ABABDABACDABABCABAB";
String pattern = "ABABCABAB";
int index = brute_force(text, pattern);
System.out.println("Brute Force: "+ index);
index = horspool(text, pattern);
System.out.println("Horspool's: "+ index);
}
Consider the following code above, now put into consideration this modification and see what appropriate changes can be done:
"The data structures HashSet (or Set)(for getting distinct characters present in the text)and HashTable (or HashMap)(for creating shift table)should be used in Horspool algorithm".
Show full java code.

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Programming Questions!