/*
 * Aresh Saharkhiz
 * saharkiz@gmail.com
 * Associate Professor / Mapua Institute of Technology / Philippines
 */

using System;
using System.Collections.Generic;
/* Test program for pattern matching of two strings */
/* Jeff Offutt, Fall 2003 */

/* Cleaned up slightly, Fall 2013 */

/* 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
{
  internal static Path p = new Path(); // INSTRUMENT

  public static void Main(string[] argv)
  {
	const int MAX = 100;
	char[] subject = new char[MAX];
	char[] pattern = new char[MAX];
	if (argv.Length != 2)
	{
	  Console.WriteLine("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)
	{
	  Console.WriteLine("Pattern string is not a substring of the subject string");
	  Console.WriteLine("Path is " + p); // INSTRUMENT

	}
	else
	{
	  Console.WriteLine("Pattern string begins at the character " + n);
	  Console.WriteLine("Path is " + p); // INSTRUMENT
	}
  }

  public virtual 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 */

	const int NOTFOUND = -1;
	int iSub = 0, rtnIndex = NOTFOUND;
	bool 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
{  
   List<int> p;
   public Path ()
   {
       p = new List<int>();
   }

   public void addNode (int i)
   {
       p.Add(i);
   }

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