package patternMatching;

public class KMP extends PatternMatcher{
	private static int[] prefixArray;
	//計算模式串的next值
	public KMP(String pattern){
		super(pattern);
		prefixArray = new int[getPattern().length()];
		int i = 0,j = 1;
		prefixArray[0] = 0;
		while(j < getPattern().length()){
			while(i > 0 && getPattern().charAt(i) != getPattern().charAt(j))//遞推
				i = prefixArray[i];
			i++;
			j++;
			if(j == getPattern().length())
				break;
			if(getPattern().charAt(j) == getPattern().charAt(i))//得出next值
				prefixArray[j] = prefixArray[i] + 1;
			else
				prefixArray[j] = i;
		}
	}
	 
	//利用next值查詢子串
	public int match(String text){
		int dPos = -1;
		int i = 0;
		int j = 1;
		while(i<text.length()){
			if(text.charAt(i) == getPattern().charAt(j)){//當前字符匹配
				if(j == (getPattern().length()-1)){//查找成功
					dPos = i - j;
					break;
				}
				i++;
				j++;
			}
			else{//當前字符不匹配
				if(prefixArray[j] == 0){
					i++;
					j = 1;
				}
				else{
					j = prefixArray[j];
				}
			}
		}
		return dPos;
	}
	 
	public static void main(String[] args) {
	  // TODO Auto-generated method stub
		KMP pattern = new KMP("abaaba");
		for(int i =0; i<prefixArray.length;i++)
		System.out.print(prefixArray[i]);
		String text = "aaaaajlsdjflskjdm";
		
	}
}