/**
 * @author Prateek Kumar Oraon (https://github.com/prateekKrOraon)
 */
import java.util.Scanner;

//An implementaion of string matching using finite automata
public class StringMatchFiniteAutomata{
	
	public static final int CHARS = 256;
	public static int[][] FA;
	public static Scanner scanner = null;
	
	public static void main(String[] args){
		
		scanner = new Scanner(System.in);
		System.out.println("Enter String");
		String text = scanner.nextLine();
		System.out.println("Enter pattern");
		String pat = scanner.nextLine();
		
		searchPat(text, pat);

		scanner.close();
		
	}
	
	public static void searchPat(String text, String pat){
		
		int m = pat.length();
		int n = text.length();
		
		FA = new int[m+1][CHARS];
		
		computeFA(pat, m ,FA);
		
		int state = 0;
		for(int i=0;i<n;i++){
			state = FA[state][text.charAt(i)];
			
			if(state == m){
				System.out.println("Pattern found at index " + (i-m+1));
			}
		}
		
	}
	
	//Computes finite automata for the partern
	public static void computeFA(String pat, int m, int[][] FA){
		
		for(int state = 0; state<= m; ++state){
			for(int x =0; x< CHARS; ++x){
				FA[state][x] = getNextState(pat, m, state, x);
			}
		}
		
	}
	
	public static int getNextState(String pat, int m, int state, int x){
		
		//if current state is less than length of pattern
		//and input character of pattern matches the character in the alphabet
		//then automata goes to next state
		if(state < m && x==pat.charAt(state)){
			return state+1;
		}
		
		for(int ns = state; ns>0; ns--){
			
			if(pat.charAt(ns-1) == x){
				
				for(int i=0; i<ns-1; i++){
					
					if(pat.charAt(i) != pat.charAt(state-ns+i+1)){
						break;
					}
					
					if(i == ns-1){
						return ns;
					}
					
				}
				
			}
			
		}
		
		return 0;
		
	}
	
}