/* Test program for pattern matching of two strings */
/* Jeff Offutt, Fall 2003 */

/* Cleaned up slightly, Fall 2013 */

import java.util.*;

/* An instrumented version of the pattern matching program. 
 * Accepts two strings of 100 characters or less, decides if
 * the second is in the first.
 * Uses the class Path to accumulate the execution path through
 * the method path(). All instrumentation statements are marked
 * with the comment "INSTRUMENT." They can easily be removed.
 */
public class TestPatInstrument
{
  static Path p = new Path();  // INSTRUMENT

  public static void main (String[] argv)
  {
    final int MAX = 100;
    char subject[] = new char[MAX];
    char pattern[] = new char[MAX];
    if (argv.length != 2)
    {
      System.out.println ("java TestPatInstrument [String Subject] [String Pattern]");
      return;
    }
    subject = argv[0].toCharArray();
    pattern = argv[1].toCharArray();
    TestPatInstrument testPat = new TestPatInstrument();
    int n = testPat.pat (subject, pattern);

    if (n == -1)
    {
      System.out.println ("Pattern string is not a substring of the subject string");
      System.out.println ("Path is " + p);  // INSTRUMENT
       
    }
    else
    {
      System.out.println
      ("Pattern string begins at the character " + n);
      System.out.println ("Path is " + p);  // INSTRUMENT
    }
  }

  public int pat (char[] subject, char[] pattern)
  {
  /* Post: if pattern is not a substring of subject, return -1
           else return (zero-based) index where the pattern (first)
           starts in subject */

    final int NOTFOUND = -1;
    int  iSub = 0, rtnIndex = NOTFOUND;
    boolean isPat  = false;
    int subjectLen = subject.length;
    int patternLen = pattern.length;

    p.addNode (1);    // INSTRUMENT
    p.addNode (2);    // INSTRUMENT

    while (isPat == false && iSub + patternLen - 1 < subjectLen)
    {
      p.addNode (3);    // INSTRUMENT
      p.addNode (4);    // INSTRUMENT
      if (subject [iSub] == pattern [0])
      {
        p.addNode (5);    // INSTRUMENT
        p.addNode (6);    // INSTRUMENT
        rtnIndex = iSub; // Starting at zero
        isPat = true;
        for (int iPat = 1; iPat < patternLen; iPat ++,
          p.addNode (6)    // INSTRUMENT
          )
	{
          p.addNode (7);    // INSTRUMENT
          if (subject[iSub + iPat] != pattern[iPat])
	  {
            rtnIndex = NOTFOUND;
            isPat = false;
            p.addNode (8);    // INSTRUMENT
            break;  // out of for loop
          }
          p.addNode (9);    // INSTRUMENT
        }
      }
      p.addNode (10);    // INSTRUMENT
      iSub ++;
    }
    p.addNode (3);    // INSTRUMENT
    p.addNode (11);    // INSTRUMENT
    return (rtnIndex);
  }
}

/* Class to accumulate the path that was executed. */
/* Use addNode (x) to add node x to the path, in order. */
/* toString() simply prints the Vector, which prints */
/* with square brackets: [1, 2, ...] */
class Path
{  
   Vector p;
   public Path ()
   {
      p = new Vector();
   }

   public void addNode (int i)
   {
      p.add (new Integer (i));
   }

   public String toString()
   {
      return p.toString();
   }
}