Substring Searching in C

The December 1988 issue of “Computer Language” had an article on substring searching in C, based on an APL algorithm. One interesting feature of the substring search function is that it returned a array that pointed to all occurances of the substring in the string. Some algorithms only return the first occurance of the substring.

The short article does not go into much detail, so I will just present the code. The program has been successfully compiled using C68. It should compile fine under Lattice C and with some work it can be converted to Small-C.

STRSRCH_C:

/* From December 1988 Computer Language */

/* This C program is based on the follwoing APL program: */

/*  $
[0] VEC #is STRING STRSRCH SUBSTG:#io:ARY
[1] | returns all positions of SUBSTG within STRING
[2] #io #is 0
[3] STRING #is.STRING & SUBSTG #is.SUBSTG
[4] ARY #is #and/(#iota #rho SUBSTG)#theta STRING #outer
    =SUBSTG
[5] VEC #is ARY/#iota #rho STRING
$ */
    
/* STRSRCH returns a pointer to an integer vector that
terminates with -1. any positive number preceding the -1
is a position of the substg within the string.  A negative
number preceding the -1 represents an error. */
      
typedef char * char_ptr;
#define sizvec 15
#define NOMEM ( char_ptr )0

int *strsrch( string, substg )
char_ptr string, substg;
{
  register int x, y;
  static int vec[ sizvec + 1 ];  /* leave room for -1 */
  unsigned int sizstg, sizsub, endsiz, *ary;
  char_ptr startmem, malloc( );
  int strlen( );
  
  sizstg = strlen( string );
  sizsub = strlen( substg );
  endsiz = sizstg - sizsub + 1;
  
/* check boundary conditions: */

  if ( ( sizstg == 0 ) && ( sizsub == 0 ) )
  {
    vec[ 0 ] = -5;
    vec[ 1 ] = -1;
    return( vec );
  }
  
  if ( sizsub == 0 )
  {
    vec[ 0 ] = -3;
    vec[ 1 ] = -1;
    return( vec );
  }
  
  if ( sizstg == 0 )
  {
    vec[ 0 ] = -2;
    vec[ 1 ] = -1;
    return( vec );
  }
  
  if ( sizsub > sizstg )
  {
    vec[ 0 ] = -6;
    vec[ 1 ] = -1;
    return( vec );
  }
  
  if ( NOMEM == ( ary = startmem = malloc( endsiz*sizeof(
int))))
  {
    vec[ 0 ] = -9;
    vec[ 1 ] = -1;
    return( vec );
  }
  
  /* Start of Algorithm */
  
  for( x = 0; x < endsiz; x++ )
     *ary++ = string[ x ] == substg[ 0 ];
       
  for( y = 1, ary = startmem; y < sizsub; y++, ary=startmem
)
     for( x = y; x < (endsiz + y); x++ )
        *ary++ &= string[ x ] == substg[ y ];
	 
  for ( y = 0, x = 0; (x < endsiz) && (y < sizvec); x++ )
     if ( *ary++ )
        vec[ y++ ] = x;
	  
  vec[ y ] = -1;
  free( startmem );
  return( vec );
}
 
STRTEST_C:

/* This function displays: */
/* The positions are: 4   29  */

#include <stdio_h>
#include "strsrch_c"

int main( )
{
  static char *stg1 = "The files are located in the file
cabinet.";
  static char *stg2 = "file";
  int *ptr;
  ptr = strsrch( stg1, stg2 );
  printf("The postitions are: ");
  while( -1 != *ptr )
     printf("%d   ",*ptr++ );
  printf("\n");
  return( 0 );
}