106 lines
3.7 KiB
Java
106 lines
3.7 KiB
Java
import java.util.*;
|
|
|
|
public class TheStates {
|
|
// Let's first create a list of all states.
|
|
private static final String[] STATES = {
|
|
"Alabama", "Alaska", "Arizona", "Arkansas", "California", "Colorado", "Connecticut",
|
|
"Delaware", "Florida", "Georgia", "Hawaii", "Idaho", "Illinois", "Indiana", "Iowa",
|
|
"Kansas", "Kentucky", "Louisiana", "Maine", "Maryland", "Massachusetts", "Michigan",
|
|
"Minnesota", "Mississippi", "Missouri", "Montana", "Nebraska", "Nevada", "New Hampshire",
|
|
"New Jersey", "New Mexico", "New York", "North Carolina", "North Dakota", "Ohio",
|
|
"Oklahoma", "Oregon", "Pennsylvania", "Rhode Island", "South Carolina", "South Dakota",
|
|
"Tennessee", "Texas", "Utah", "Vermont", "Virginia", "Washington", "West Virginia",
|
|
"Wisconsin", "Wyoming"
|
|
};
|
|
|
|
|
|
public static void main(String[] args) {
|
|
Scanner scanner = new Scanner(System.in);
|
|
int choice;
|
|
|
|
while (true) {
|
|
System.out.println("");
|
|
System.out.println("Menu:");
|
|
System.out.println("1 - Display the text");
|
|
System.out.println("2 - Search");
|
|
System.out.println("3 - Exit program");
|
|
System.out.print("Enter your choice: ");
|
|
choice = scanner.nextInt();
|
|
scanner.nextLine(); // consume newline
|
|
|
|
switch (choice) {
|
|
case 1:
|
|
System.out.println("\nText containing all states:\n");
|
|
System.out.println(STATESLIST);
|
|
break;
|
|
|
|
case 2:
|
|
System.out.print("\nEnter a pattern to search: ");
|
|
String pattern = scanner.nextLine();
|
|
List<Integer> results = boyerBadCharSearch(STATESLIST, pattern);
|
|
if (results.isEmpty()) {
|
|
System.out.println("Pattern not found.");
|
|
} else {
|
|
System.out.println("Pattern found at indices: " + results);
|
|
}
|
|
break;
|
|
|
|
case 3:
|
|
System.out.println("Exiting program.");
|
|
scanner.close();
|
|
return;
|
|
|
|
default:
|
|
System.out.println("Invalid option. Try again.");
|
|
}
|
|
}
|
|
}
|
|
|
|
// Create a single string containing all state names separated by a dash
|
|
private static final String STATESLIST = String.join(" - ", STATES);
|
|
|
|
// Boyer-Moyer bad character search
|
|
public static List<Integer> boyerBadCharSearch(String text, String pattern) {
|
|
|
|
List<Integer> result = new ArrayList<>();
|
|
int[] badChar = buildBadCharTable(pattern);
|
|
int m = pattern.length();
|
|
int n = text.length();
|
|
int shift = 0;
|
|
|
|
while (shift <= (n - m)) {
|
|
int j = m - 1;
|
|
|
|
// Move from right to left of the pattern
|
|
while (j >= 0 && pattern.charAt(j) == text.charAt(shift + j))
|
|
j--;
|
|
|
|
if (j < 0) {
|
|
result.add(shift);
|
|
if (shift + m < text.length()) {
|
|
shift += m - badChar[text.charAt(shift + m)];
|
|
} else {
|
|
shift += 1;
|
|
}
|
|
} else {
|
|
shift += Math.max(1, j - badChar[text.charAt(shift + j)]);
|
|
}
|
|
}
|
|
|
|
return result;
|
|
}
|
|
|
|
// Build bad character table
|
|
public static int[] buildBadCharTable(String pattern) {
|
|
final int SIZE = 256;
|
|
int[] table = new int[SIZE];
|
|
Arrays.fill(table, -1);
|
|
|
|
for (int i = 0; i < pattern.length(); i++) {
|
|
table[pattern.charAt(i)] = i;
|
|
}
|
|
|
|
return table;
|
|
}
|
|
}
|