プログラマ専用SNS ミクプラ

コード:

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

#define SUFSIZE 256
#define SASIZE 1000

int matchN = 0;
char match[SASIZE][SUFSIZE];
int matchIdx[SASIZE];
char sfx[SASIZE][SUFSIZE];
int idx[SASIZE][SUFSIZE];
int max = 0;

int make_sa( char str[] )
{
  int i, j;
  int n = max;
  for ( i = 0; i < strlen( str )-1;  i++ )
  {
    char buf[SUFSIZE];
    int m = 0;
    for ( j = i; j < strlen( str ) - 1; j++ )
    {
      buf[m] = str[j];
      m++;
      if ( m == SUFSIZE ){ break; }
    }
    buf[m] = '\0';
    strcpy( sfx[n], buf );
    n++;
  }
  max = n;
  return 1;
}

/* 接尾辞配列を作成する */
int open_file( char path[] )
{
  FILE* fp = fopen(path, "r");
  if ( fp == NULL ){ 
    printf("file open error.\n");
    return -1; 
  }
  char s[SUFSIZE];
  int n = 0;
  while( fgets( s, SUFSIZE, fp ) != NULL )
  {
    make_sa( s );
    n++;
  }
  fclose(fp);
  return 1;
}

/* 接尾辞配列をソート */
int sort_suffix_array()
{
  int i, j;
  int cmp;
  char tmp[SUFSIZE];
  for ( i = 0; i < max; i++ )
  {
    for ( j = i+1; j < max; j++ )
    {
      cmp = strcmp( sfx[i], sfx[j] );
      if ( cmp > 0 )
      {
	strcpy( tmp, sfx[i] );
	strcpy( sfx[i], sfx[j] );
	strcpy( sfx[j], tmp );
      }
    }
  }
  return 1;
}

/* 文字列stが接尾辞sfの中に含まれるなら1以上の値を返す */
int strcheck( char sf[], char st[] )
{
  int i, j;

  for ( i = 0; i < strlen( sf ); i++ )
  {
    if ( st[0] == sf[i] )
    {
      int flg = 1;
      int m = 1;
      for ( j = 1; j < strlen( st ); j++ )
      {
	if ( sf[i+m] != st[j] )
	{ 
	  flg = 0;
	  break;
	}
	m++;
      }
      if ( flg == 1 )
      {
	return m;
      }
    }
  }
  return 0;
}

/* 接尾辞配列から，パターン ptn を */
/* 二分探索により検索 */
int bin_search( char ptn[] )
{
  int pos;
  int low = 0;
  int high = max - 1;
  int mid = 0;
  int cmp = 0;
  int check = 0;
  while( low <= high )
  {
    mid = ( low + high ) / 2;
    
    cmp = strcmp( sfx[mid], ptn );
    check = strcheck( sfx[mid], ptn );
    if ( check > 0 && cmp != 0 )
    {
      char buf[SUFSIZE];
      strcpy( match[matchN], sfx[mid] );
      matchIdx[matchN] = mid;
      matchN++;
    }

    if ( cmp == 0 )
    {
      return mid;
    }
    else if ( cmp < 0 )
    {
      low = mid + 1;
    }
    else if ( cmp > 0 )
    {
      high = mid - 1;
    }
  }
  return -1;
}



int main( int argc, char* argv[] )
{

  open_file( argv[1] );

  sort_suffix_array();
  int i, j;
  int x = bin_search( argv[2] );
  if ( x >= 0 )
  {
    printf("exact match: [%s] [%d]\n", sfx[x], x );
  }
  else if ( matchN > 0 )
  {
    for ( i = 0; i < matchN; i++ )
    {
      printf("partial match: [%s] [%d]\n", match[i], matchIdx[i] );
    }
  }
  else{
    printf("文字列 [%s] は，ファイル\"%s\"内に見つかりませんでした。\n", argv[2], argv[1] );
  }

}

コード:

if ( x >= 0 )
  {
    printf("exact match: [%s] [%d]\n", sfx[x], x );
  }
  else if ( matchN > 0 )
  {
    for ( i = 0; i < matchN; i++ )
    {
      printf("partial match: [%s] [%d]\n", match[i], matchIdx[i] );
    }
  }
  else{
    printf("文字列 [%s] は，ファイル\"%s\"内に見つかりませんでした。\n", argv[2], argv[1] );
  }