(* Given an array of strings and a string, see how many paths there
   are through th matrix that trace out the string *)
   
fun trace_string( matrix , str ) =
let
  (* mash the strings of the matrix into one big string(array) *)
  val bigstr = String.concat( matrix )
  
  val columns = String.size( List.hd( matrix ) )
  val rows = List.length( matrix ) 

  (* the size of the intermediate arrays we will compute *)  
  val asize = columns * rows

  (* create an array of our needed size by calling function 'x' repeatedly
     with the index of the array slot, and putting the results into the 
     specified index *)
  fun atab( func ) = Array.tabulate( asize , func )
  
  (* since we're using a 1-d array to compute the paths, precompute the neighbors
     of each cell of the array, and store that in an array.  
     There's a bit of bouncing back and forth between 
     col,row and index.  I suppose there is room for optimization here *)
  fun cell_in_bounds( col , row ) = col >= 0 andalso row >= 0 andalso col < columns andalso row < rows
  
  fun cell_to_index( col , row ) = row * columns + col
  fun index_to_cell( index ) = ( index mod columns , index div columns )
  
  val neighbor_cell_deltas = [(~1,~1),(0,~1),(1,~1),(~1,0),(1,0),(~1,1),(0,1),(1,1)]
  
  (* make a list of cells that could be neighbors but may be off the matrix *)
  fun potential_neignbors_of( col , row ) = 
    List.map ( fn( cd , rd ) => ( col + cd , row + rd ) ) neighbor_cell_deltas
    
  (* filter out the neighbors that would be out-of-bounds *)  
  fun neighbors_for( col , row ) = 
    map cell_to_index ( List.filter cell_in_bounds( potential_neignbors_of( col , row ) ) ) 
  
  (* finally, make the lookup table for neighbors of each cell *)
  val neighbors = atab( fn( index ) => neighbors_for( index_to_cell( index ) ) )
  
  (* compute the sum of all the legal neighbor cells. *)
  fun sum_of_neighbors( arr , neighbors ) =
    List.foldl ( fn( neighbor , sum) => Array.sub( arr , neighbor ) + sum ) 0 neighbors;
  
  (* the value of a cell is the sum of its neighbors it it matches the current 
     string position.  Otherwise, it is zero.  Fill is used to special case the first
     character of the path, to give it a value of one when all the neighbors are zero.
     This is a bit grungy, but better than making a special starting matrix special-cased
     to the first character of the string, imo *)
  fun cell_value( arr , index , chr , fill ) = 
    if String.sub( bigstr , index ) = chr 
      then fill + sum_of_neighbors( arr , Array.sub( neighbors , index ) )
      else 0
 
  (* finally, compute the sum vectors.  If we are at the end of the string, sum
     the vector; this will be the number of legal paths.  Otherwise, use the 
     current character in the string and the last vector(computed for the last character) 
     to compute the current vector.  Note from above that 'fill' is one for the first recursion,
     then it is zero thereafter *)
  fun walk_path( arr , [] , _ ) = Array.foldl (op +) 0 arr |
      walk_path( arr , chr::chrs , fill ) =
        walk_path( atab( fn( index ) => ( cell_value( arr , index , chr , fill ) ) ) , chrs , 0 ) 
    
in
  (* finally, the main section.  Start with a vector initialized to one *)
  walk_path( Array.array( asize , 0 ) , explode( str ) , 1 )
end;
  
fun ts() = trace_string( [ "aa" , "aa" ] ,  "aa" );

fun t3() = trace_string( [ "aaaa" , "aaaa" , "aaaa" , "aaaa" ] , "aaaa" );