KnuthMorrisPratt - dfa can be modifiable by re defining the range - longest proper prefix which is also suffix method

KMP.java

/******************************************************
 * KNUTH MORRIS PRATT SUBSTRING SEARCH
 * 
 * Initially computes a DFA array which tells us the restart 
 * state of the pattern while the txt goes from left to right
 * without any change in the increment 
 * 
 * Search plays with the state of the pattern variable
 * 
 * Time: O(N)
 * Space: Storage(false) - No backup of text is required 
 * 
 ******************************************************/
public class KMP {
	
	private String pat;
	private int[][] dfa;
	
	public KMP(String pat){
		this.pat = pat; 
		int R = 256,M = pat.length(); 
		dfa = new int[R][M];
		
		dfa[pat.charAt(0)][0]=1;
		for(int X=0,j=1;j<M;j++){
			
			for(int c=0; c<R; c++){
				dfa[c][j]=dfa[c][X];
			}
			dfa[pat.charAt(j)][j] =j+1;
			X = dfa[pat.charAt(j)][X];			
		}		
	}
	
	public int search(String txt){
		int N = txt.length(),M = pat.length();
		int i,j;
		for(j=0, i=0;i<N && j<M; i++){
			j = dfa[txt.charAt(i)][j];
			//StdOut.println("Value of (j,i):"+j+","+i);
		}
		
		if(j==M) return i-M;
		else return N;
	}
	
	public static void main(String args[]){
		//Take the pattern and text from input
		KMP kmp = new KMP(pat);
		int val = kmp.search(txt);
		if(val<N) StdOut.println(txt.substring(val,val+M));
		else StdOut.println("Match not found !");
	}	

}

/********************************************************
	LONGEST PREFIX SUFFIX - lps[] -
	computes lpngest prefix of pat which is also suffix of pat
*********************************************************/
void KMPSearch(String pat,String txt){
	int M = pat.length(),N = txt.length();
	int[] lps = new int[M];
	
	computeLPSArray(pat,lps,M);
	int j=0; //pattern in char position
	while(i<N){
		if(txt.charAt(i)==pat.charAt(j)){
			i++;j++;
		} 
		if(j==M){//Found pattern at i-M
			j=lps[j-1];
		} else if(i<N && txt.charAt(i)!=pat.charAt(j)){
			if(j!=0) j=lps[j-1];
			else i++;
		}
	}
	
}

void computeLPSArray(String pat,int[] lps,int M){
	int len=0,i=1;
	lps[0]=0;
	while(i<M){
		if(pat.charAt(i)==pat.charAt(len)){
			lps[i++]=++len;
		} else {
			if(len!=0){
				len=lps[len-1];
			} else {
				lps[i++]=len;
			}
		}
	}	
}