Return to Question

Boyer Moore version

 final BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
 final int number_trials = Integer.valueOf(input.readLine());
 
 for(int trial_number = 0; trial_number < number_trials; trial_number++)
 { 
 final StringBuilder builder = new StringBuilder();
 final int MISMATCH_TOLERANCE = 1;
 final int ALPHABET_SIZE = 26;
 final int[] pattern_skip = new int[ALPHABET_SIZE];
 final char[] text = input.readLine().toCharArray();
 final char[] pattern = input.readLine().toCharArray();
 int skip_value = 0;
 
 Arrays.fill(pattern_skip, -1);
 for(int pattern_index = 0; pattern_index < pattern.length; pattern_index++)
 {
 pattern_skip[pattern[pattern_index] - 97] = pattern_index;
 }
 for(int text_index = 0; text_index <= text.length - pattern.length; text_index += skip_value)
 {
 int missed_characters = 0;
 skip_value = 0;
 
 for(int pattern_index = pattern.length - 1; pattern_index >= 0; pattern_index--)
 {
 if(pattern[pattern_index] != text[text_index + pattern_index] && ++missed_characters > MISMATCH_TOLERANCE)
 {
 skip_value = Math.max(1, pattern_index - pattern_skip[text[text_index + pattern_index] - 97]);
 break;
 }
 }
 
 if(missed_characters <= MISMATCH_TOLERANCE)
 {
 builder.append(text_index);
 builder.append(" ");
 skip_value++;
 }
 } 
 
 if(builder.length() > 0 && builder.charAt(builder.length() - 1) == ' ')
 {
 builder.deleteCharAt(builder.length() - 1);
 } 
 
 System.out.println(builder.toString()); 
 }

Boyer Moore version

 final BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
 final int number_trials = Integer.valueOf(input.readLine());
 
 for(int trial_number = 0; trial_number < number_trials; trial_number++)
 { 
 final StringBuilder builder = new StringBuilder();
 final int MISMATCH_TOLERANCE = 1;
 final int ALPHABET_SIZE = 26;
 final int[] pattern_skip = new int[ALPHABET_SIZE];
 final char[] text = input.readLine().toCharArray();
 final char[] pattern = input.readLine().toCharArray();
 int skip_value = 0;
 
 Arrays.fill(pattern_skip, -1);
 for(int pattern_index = 0; pattern_index < pattern.length; pattern_index++)
 {
 pattern_skip[pattern[pattern_index] - 97] = pattern_index;
 }
 for(int text_index = 0; text_index <= text.length - pattern.length; text_index += skip_value)
 {
 int missed_characters = 0;
 skip_value = 0;
 
 for(int pattern_index = pattern.length - 1; pattern_index >= 0; pattern_index--)
 {
 if(pattern[pattern_index] != text[text_index + pattern_index] && ++missed_characters > MISMATCH_TOLERANCE)
 {
 skip_value = Math.max(1, pattern_index - pattern_skip[text[text_index + pattern_index] - 97]);
 break;
 }
 }
 
 if(missed_characters <= MISMATCH_TOLERANCE)
 {
 builder.append(text_index);
 builder.append(" ");
 skip_value++;
 }
 } 
 
 if(builder.length() > 0 && builder.charAt(builder.length() - 1) == ' ')
 {
 builder.deleteCharAt(builder.length() - 1);
 } 
 
 System.out.println(builder.toString()); 
 }

I was working on the challenge "Save Humanity " from Interviewstreet for a while then gave up, solved a few other challenges, and have come back to it again. The code itself generates the correct answers but the time complexity (O(text * pattern)) is not sufficient for the auto-grader. Could anyone perhaps give me a hint or a pointer on how to improve my algorithm?

final BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
final StringBuilder builder = new StringBuilder();
final int number_trials = Integer.valueOf(input.readLine());

for(int trial = 0; trial < number_trials; trial++)
{ final int allowed_mismatches = 1;
 final char[] text = input.readLine().toCharArray();
 final char[] pattern = input.readLine().toCharArray(); input.readLine();
 
 for(int text_index = 0; text_index < text.length - pattern.length + 1; text_index++)
 {
 int pattern_index = 0;
 int missed = 0;
 
 while(pattern_index < pattern.length && missed <= allowed_mismatches)
 {
 if(text[text_index + pattern_index] != pattern[pattern_index])
 {
 missed++;
 }
 
 pattern_index++;
 }
 
 if(missed <= allowed_mismatches)
 {
 builder.append(text_index);
 builder.append(" ");
 }
 }
 
 if(builder.length() > 0 && builder.charAt(builder.length() - 1) == ' ')
 {
 builder.deleteCharAt(builder.length() - 1);
 } 
 
 if(trial + 1 < number_trials)
 {
 builder.append("\n");
 } 
}

System.out.println(builder.toString());

I was working on the challenge Save Humanity from Interviewstreet for a while then gave up, solved a few other challenges, and have come back to it again.

The code below generates the correct answers but the time complexity O(text * pattern) is not sufficient for the auto-grader. Could anyone perhaps give me a hint or a pointer on how to improve my algorithm?

final BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
final StringBuilder builder = new StringBuilder();
final int number_trials = Integer.valueOf(input.readLine());
for(int trial = 0; trial < number_trials; trial++)
{ final int allowed_mismatches = 1;
 final char[] text = input.readLine().toCharArray();
 final char[] pattern = input.readLine().toCharArray(); input.readLine();
 
 for(int text_index = 0; text_index < text.length - pattern.length + 1; text_index++)
 {
 int pattern_index = 0;
 int missed = 0;
 
 while(pattern_index < pattern.length && missed <= allowed_mismatches)
 {
 if(text[text_index + pattern_index] != pattern[pattern_index])
 {
 missed++;
 }
 
 pattern_index++;
 }
 
 if(missed <= allowed_mismatches)
 {
 builder.append(text_index);
 builder.append(" ");
 }
 }
 
 if(builder.length() > 0 && builder.charAt(builder.length() - 1) == ' ')
 {
 builder.deleteCharAt(builder.length() - 1);
 } 
 
 if(trial + 1 < number_trials)
 {
 builder.append("\n");
 } 
}
System.out.println(builder.toString());