/**
 * 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 SubStringSearch
{
    public static void main ( String [] args )
    {
        Scanner keyboard = new Scanner(System.in);
        char []target;
        char []key;
        String input;

        // 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) + "\"");
   
        // position keeps track of position of match
        // initialize position = -1, meaning not found
        int position = -1;
        for ( int i = 0; i <= target.length - key.length; i++ )
        {
            // 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 found records whether or not position i in the
            // target is a match for the key.   We initially assume
            // found 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 found = true;
            for ( int j = 0; j < key.length; j++ )
            {
                if ( key[j] != target[i+j] )
                    found = false;
            }
            
            // If found is still true and we have not yet recorded a matching
            // position, then record this position.
            if ( found && position == -1 )
                position = i;
        }
        
        // once done searching, now print final message
        if ( position == -1 )
            System.out.println("Key not found");
        else
            System.out.println("Key found at index " + position );
    }
}