// Introduction to Software Testing
// Authors: Paul Ammann & Jeff Offutt
// Chapter 2, section 2.3, page 61


import java.util.*;

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 Path {  
     Vector p;
     public Path () {
        p = new Vector();
     }
     public void addNode(int i) {
        p.add(new Integer(i));
     }
     public String toString() {
        return p.toString();
     }
  }