boyermoore.java

来自「三种字符串匹配：BF」· Java 代码 · 共 56 行

package patternMatching;
import java.util.Hashtable;
public class BoyerMoore extends PatternMatcher {
	private static Hashtable<Character, Integer> lastOccurence;
	int l = 0;
	public BoyerMoore(String pattern) {
		super(pattern);
		comparetimes = 0;
		lastOccurence = new Hashtable<Character, Integer>();
		for (int i= getPattern().length()-1 ; i>=0 ; i--){
			if(!lastOccurence.containsKey(getPattern().charAt(i))){
				lastOccurence.put(getPattern().charAt(i), i);
			}
		}
		//System.out.println(lastOccurence.toString());
	}
	public int match(String text){
		int i = getPattern().length()-1;
		int j = i;
		while( i < text.length()){
			if (text.charAt(i)== getPattern().charAt(j)){
				if (j==0){
					return i;
				}
				else {
					i--;
					j--;
				}
			}
			else {
				if(lastOccurence.containsKey(text.charAt(i))){
					l = lastOccurence.get(text.charAt(i))+1;
				}
				else {
					l = 0;
				}
				i = i + getPattern().length() - Math.min(j, l );
				j = getPattern().length() - 1;
			}
			comparetimes++;
		}
		return -1;
	}
	public long getComparetimes() {
		return comparetimes;
	}
	// TODO test!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
	public static void main(String[] args) {
		BoyerMoore pattern = new BoyerMoore("j??lsdjflskjdm");
		String text = "aaaaaaaaaaabbbcdabbksfj??lsdjflskjdm";
		System.out.println(pattern.match(text));
		System.out.println(pattern.comparetimes);
		//System.out.println(lastOccurence.size());
	}
}