package taskPkg;

import java.util.Scanner;

public class SubArray {

	public static void main(String[] args) {
		// FINDING SUBARRAY AND ITS POSITION
		System.out.println("Enter a sentence to search in.");
		Scanner scn = new Scanner(System.in);
		String sentn = scn.nextLine();
		System.out.println("Enter a word to be searched.");
		String word = scn.next();
		scn.close();
		char[] sentence = sentn.toCharArray();
		char[] key = word.toCharArray();
		int n = sentence.length, m = key.length;
		int i = 0, j = 0, st = 0; // i- maintain index in the sentence, j-maintain index in key
		boolean match = false;
		while (i < n && j < m) {// 
			//System.out.println("i=" + i + "     sentence[i]=" + sentence[i] + "    j=" + j + "   key[j]=" + key[j]);
			if (sentence[i] == key[j]) { //if it matches incrementing both pos
				i++;
				j++;
				if (j == m) { //if the key reaches end, made the match and exit
					match = true;
					break;
				}
			} 
			else {    // if no match move on to the next letter, but key should start from 0
				j = 0;
				i=st+1;
				st = i;  // this is to save the starting of the subarray
			}
		}
		if (match)
			System.out.println("SubArray is found at " + st);
		else
			System.out.println("SubArray is not found");
	}
}