刚开始学习java。我无法弄清楚散列的主题。 错误正是在哈希码的计算中。 window_hash == pattern_hash 总是返回 false 虽然这不可能,因为在 3 14 16 位置上肯定存在巧合。 这是代码:
import java.util.ArrayList;
public class Main {
public static void main(String[] args) {
String source = "Alibaba or Alibubab? I do not know!";
String pattern = "b*b";
ArrayList result = defSearch(source, pattern);
if (result != null) {
System.out.println("Подстрока, найденная в позициях: " + result);
}
}
static ArrayList<Integer> defSearch(String source, String pattern) {
if (source.length() < pattern.length()) {
System.out.println("Такой подстроки точно нет!");
return null;
}
ArrayList<Integer> found = new ArrayList<>();
int pattern_hash = 0;
int asterik_position = pattern.indexOf('*');
for (int i = 0; i < pattern.length(); i++) {
if (i != asterik_position) {
pattern_hash += pattern.charAt(i);
}
}
for (int start = 0; start < source.length() - pattern.length() + 1; start++) {
int window_hash = 0;
if (start == 0) {
for (int i = 0; i < pattern.length(); i++) {
if (i != asterik_position) {
window_hash += source.charAt(start + i);
}
}
window_hash -= source.charAt(asterik_position);
} else {
window_hash -= source.charAt(start - 1);
window_hash += source.charAt(start + pattern.length() - 1);
window_hash += source.charAt(start - 1 + asterik_position);
window_hash -= source.charAt(start + asterik_position);
}
if (window_hash == pattern_hash) {
boolean match = true;
for (int i = 0; i < pattern.length(); i++) {
if (i != asterik_position && pattern.charAt(i) != source.charAt(start + i)) {
match = false;
break;
}
}
if (match) {
found.add(start);
}
}
}
return found;
}
这个话题不像其他话题那么容易给出。请帮助。