knuthmorrispratt.java

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

package patternMatching;

public class KnuthMorrisPratt extends PatternMatcher {
	private int[] prefixArray;
	public KnuthMorrisPratt(String pattern) {
		super(pattern);
		comparetimes=0;
		prefixArray = new int[getPattern().length()];
		int i = 1;
		int matches = 0;
		while (i< getPattern().length()){
			if (getPattern().charAt(i) == getPattern().charAt(matches)){
				matches++;
				prefixArray[i] = matches;
				i++;
			}
			else if (matches> 0){
				matches = prefixArray[matches-1];
			}
			else {
				i++;
			}
		}
	}	
	public int match(String text) {
		int i = 0;
		int matches = 0;
		while(i < text.length()){
			if(text.charAt(i)==getPattern().charAt(matches)){
				matches++;
				if(matches == getPattern().length()){
					return i-getPattern().length()+1;
				}
				else{
					i++;
				}
			}
			else if (matches > 0){
				matches = prefixArray[matches -1];
			}
			else{
				i++;
			}
			comparetimes++;
		}
		return -1;
	}
	public long getComparetimes() {
		return comparetimes;
	}
// TODO test!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
	public static void main(String[] args) {
		PatternMatcher pattern = new KnuthMorrisPratt("j??lsdjflskjdm");
		String text = "aaaaaaaaaaabbbcdabbksfj??lsdjflskjdm";
		System.out.println(pattern.match(text));
		System.out.println(pattern.comparetimes);
		pattern = new KnuthMorrisPratt("j??lsdjflskjdm");
		String text1 = "aaaaaaaaaaabbbcdabbksfj??lsdjflskjdm";
		System.out.println(pattern.match(text1));
		System.out.println(pattern.comparetimes);
	}
}