/**
 * Matt Kretchmar
 * February 22, 2006
 * SubStringSearch.java
 * This program prompts the user for two strings, a larger target
 * and a smaller key.  The purpose of the program is to search for
 * the key inside the target string. If the key is found, an index 
 * of the first occurrence is reported, otherwise a "not found" 
 * message is presented.
 */
import java.util.Scanner;

class SubStringSearch2
{
    public static void main ( String [] args )
    {
        Scanner keyboard = new Scanner(System.in);
        char []target;
        char []key;
        String input;
        boolean found = false;

        // read target and key from user
        System.out.println("Enter target string: ");
        input = keyboard.nextLine();
        target = input.toCharArray();
        System.out.println("Enter key string: ");
        input = keyboard.nextLine();
        key = input.toCharArray();
        
        System.out.println( "Searching for key [" + String.valueOf(key) + 
                        "] in target \"" + String.valueOf(target) + "\"");
   
        int i = 0;
        while ( i <= target.length - key.length && !found )
        {
            // i is starting index in target of potential match.  
            // i must start at 0 (first index in target) and 
            // progress through all possible starting points in the 
            // target string.  
            
            // boolean isMatch records whether or not position i in the
            // target is a match for the key.   We initially assume
            // isMatch is true and set it to false if we find any
            // character in the key which does not match the corresponding
            // character in the target (starting from position i).
            boolean isMatch = true;
            int j = 0;
            while ( j < key.length && isMatch)
            {
                if ( key[j] != target[i+j] )
                    isMatch = false;
                j++;
            }
            
            // If isMatch is still true and we have not yet recorded a matching
            // position, then record this position.
            if ( isMatch )
                found = true;
            
             i++;
        }
        
        // once done searching, now print final message
        if ( found )
            System.out.println("Key found at index " + (i-1) );
        else
            System.out.println("Key not found");
    }
}