// this code implements the string matching algorithm with finite
// automaton. It generates random text T and pattern P strings of the
// lengths given by the first two command line parameters.
//
// 1. Save this file as AutomatMatch.java
// 2. Compile it with javac AutomatMatch.java
// 3. Run it with java AutomatMatch 10000000 20 (or n iand m of your choice)

import java.util.*;

public class AutomatMatch
{
  public static void main(String[] args)
  {
    int n = Integer.parseInt(args[0]);  // text length
    int m = Integer.parseInt(args[1]);  // pattern length
    int d = 10;                          // alphabet size
    System.out.print("Generating random text and pattern ... ");

    byte[] T = generateString(n, d);
    byte[] P = generateString(m, d);
//    P[0] = 0; P[1] = 1; P[2] = 0; P[3] = 1; P[4] = 0; P[5] = 2; P[6] = 0;

    for (int i=0; i<m; i++)             // making sure that the pattern
      T[n-2*m+i] = P[i];                // occurs at the tail of T
    if (n < 80)
    {
      System.out.print("\nT = \"");         // print T
      for (int i=0; i<n; i++)
        System.out.print((char)(T[i] +48));
      System.out.println("\"");
    }
    System.out.print("done \nP = \"");  // Print P
    for (int i=0; i<m; i++)
      System.out.print((char)(P[i] +48));
    System.out.println("\"\n");
   
    // applying the brut force text search algorithm
    System.out.println("Running the brut force method ...");
    boolean match = true; 
    for (int s=0; s<=n-m; s++)
    {
      match = checkMatch(T, P, s);
      if (match)
      {
        System.out.println("Pattern occurs with shift " + s + "\n");
        break;
      }
    }
    if (! match)
      System.out.println("Pattern not found");

    // the automaton-based algorithm
    System.out.println("Running the automaton method ...");
    int[][] delta = computeTransitFunction(P, d);

    // print out the transition function
    if (m < 10)
    {
      System.out.println("The transition function:");
      for (int i=0; i<delta.length; i++)
      {
        for (int j=0; j<d; j++)
          System.out.print(delta[i][j] + " ");
        System.out.println();
      }
    }

    // running the search
    int s = finiteAutomatMatcher(T, delta, m);
    if (s >= 0)
       System.out.println("Pattern occurs with shift " + s + "\n");
    else
       System.out.println("Pattern not found");
  }

  public static int[][] computeTransitFunction(byte[] P, int d)
  {
    int m = P.length;                    // line 1
    int[][] delta = new int[m+1][d];     // array to be returned 
    byte[] PP = new byte[m+1];           // aux. array for implementation
    for (int i=0; i<P.length; i++)       // copying P to PP
      PP[i] = P[i]; 

    for (int q=0; q<=m; q++)             // line 2
    {
      for (int a=0; a<d; a++)            // line 3
      { 
        int k = Math.min(m, q+1);        // line 4

        byte temp = PP[q];               // temporarily save PP[q]
        PP[q] = (byte)a;                 // PP[q+1] = P[q]a
        while (k >= 0)
        {
          boolean suffix = true;         // check for P[k] being suffix of 
          for (int j=0; j<k; j++)        // P[q]a in lines 5-6
          {      
            if (P[k-1-j] != PP[q-j])     // if the characters do not match
            {                            
              k--;                       // decrement k and start over
              suffix = false;
              break;
            }
          }
          if (suffix) break;             // P[k] is a suffix of P[q]a
        }
//        System.out.println("delta[" + q + "][" + a + "]=" + k);

        delta[q][a] = k;                 // line 7
        PP[q] = temp;                    // restore original PP
      }
    }
    return(delta);                       // line 8
  }

  // this method returns the shift of the first match of P in T
  // if no match is found, the value -1 is returned
  public static int finiteAutomatMatcher(byte[] T, int[][] delta, int m)
  {
    int q = 0;
    for (int i=0; i<T.length; i++)
    {
      q = delta[q][T[i]];
      if (q == m)            // match is found
        return(i-m+1);       // report it (array T is indexed starting with 0)
    }
    return(-1);              // match is not found
  }

  // this method generates a random array of (non-negative) bytes of a 
  // given length and range
  public static byte[] generateString(int n, int d)
  {
    Calendar cal = Calendar.getInstance();    // set up the random numbers
    long seed = cal.getTimeInMillis();        // generator
    Random generator = new Random(seed);
    byte[] arr = new byte[n];                 // set up random array of bytes
    for (int i=0; i<n; i++)
      arr[i] = (byte) generator.nextInt(d);
    return(arr);
  }

  // this function checks the patterm string P and text T at shift s for
  // a match
  public static boolean checkMatch(byte[] T, byte[] P, int s)
  {
    boolean match = true;
    for (int i=0; i<P.length; i++)
    if (T[s+i] != P[i])
    {
      match = false;
//      break;       // this line is taken off to model "real world" data
    }
    return(match);
  }
}