/* 
*
*  Z-value computation
*
* Author: Mihai Pop (2009)
*
* Computes the Z-values as described by Gusfield as 
* "fundamental string processing"
*
* Limitations of code: 
*   Code reads the string from the user (should be more flexible).
*   Memory is statically allocated (should be dynamic). 
*
*/

#include <stdio.h>
#include <string.h>

/* Simple matching function
*
* Returns # characters matching between beginning of string
* and string starting at position i
*/
int match(int i, char *s)
{
  int k; /* index in matched region */
   
  for (k = 0; k < strlen(s) - i; k++) {
/*    printf ("Matching %c with %c\n", s[k], s[i + k]);*/
    if (s[k] != s[i + k]) 
      return k;
  }

  return strlen(s) - i;
} /* end match */

/* Here we go */
int main (int argc, char *argv[])
{
  /* The string */
  char String[256];

  /* Where the z-values will go */
  int Z[256];

  /* The farthest reaching j,Z[j] pair */
  int jmax = 0;
  int zmax = 0;

  /* where we compute the Z value */
  int i = 0;


  /* first read in the string */
  printf("Please type in the string:\n");
  scanf("%s", String);

  Z[0] = 0; /* by definition */

  /* Now compute Z-values one by one */
  for (i = 1; i < strlen(String); i++) {
    /* Loop invariant: jmax + zmax are maximal over all j + Z[j] < i */
    
    /* printf("S[i] = %c i = %d jmax = %d zmax = %d ", String[i], i, jmax, zmax);*/
    if (i > jmax + zmax - 1) { /* simple case - need to match */
      Z[i] = match(i, String);
        if (Z[i] > 0) {
          jmax = i;
	  zmax = Z[i];
	}
      /*printf ("case 0:  Z[i] = %d\n", Z[i]);*/
    } else { /* here's the tough work */
      /* case I */
      if (Z[i - jmax] < jmax + zmax - i) {
        Z[i] = Z[i - jmax];
        /*printf ("case 1: Z[i - jmax] = %d Z[i] = %d\n", Z[i - jmax], Z[i]);*/
      }

      /* case II */
      if (Z[i - jmax] > jmax + zmax - i) {
	Z[i] = jmax + zmax - i;
        /*printf ("case 2: Z[i - jmax] = %d Z[i] = %d\n", Z[i - jmax], Z[i]);*/
      }

      /* case III */
      if (Z[i - jmax] == jmax + zmax - i) {
        Z[i] = Z[i - jmax] + match(zmax + jmax, String + Z[i - jmax]);
        /* printf ("case 3: Z[i - jmax] = %d Z[i] = %d S[zmax + jmax] = %c S[Z[i - jmax] + 1] = %c nmatch = %d\n", Z[i - jmax], Z[i], String[zmax + jmax], (String + Z[i - jmax] + 1)[0], match(zmax + jmax, String + Z[i - jmax] + 1));*/
        jmax = i;
        zmax = Z[i];
      }
    }
  } /* end for loop */ 

  /* now time to print our hard work */

  printf("\n\n"); /* make some room */
  printf("S = ");
  for (i = 0; i < strlen(String); i++) 
    printf("%3c", String[i]); /* leave spaces to align z-values */
  printf("\n\n");

  printf("Z = ");
  for (i = 0; i < strlen(String); i++)
    printf("%3d", Z[i]);
  printf("\n");

  exit(0); /* finish gracefully */
} /* end main */