• TOP /
• BBS /
• #99 プログラム技術 /
• Article 1014

• Older
• Newer

#99 Article 1014 Posted at 1995/12/11 02:52:23 by ＢＡＡ (MAP5104) [SAHOU.2]

Subject: Re: プログラミング作法・お題２ /995

まずお約束の C です。
ファイルと検索文字列は任意のものにしました。
----------------------------------------
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char *progName;			/* argv[0] */

void usage ()
{
  fprintf (stderr, "usage: %s search_string filename.\n", progName);
  exit (1);
}

void error (char *s)
{
  fprintf (stderr, "%s: %s\n", progName, s);
  exit (1);
}

/* fp に含まれる文字列 searchStr の数を数える。 */

/* fp からの入力と searchStr の index 番目の文字を一文字毎に比較する。 */
/* 一致した場合は index を +1 する。そして、index が文字列の長さになっ */
/* たら、カウンタを +1 して index を 0 に戻す。一致しない場合は、適当 */
/* な位置まで index を戻す。 */
int countString (FILE *fp, char *searchStr)
{
  int counter;
  int searchStrLen;
  int index;
  int *backIndex;
  int c;
  int i,j;

  searchStrLen = strlen (searchStr);
  if ((backIndex = malloc (sizeof (int) * searchStrLen)) == NULL)
    error ("Out of memory.");
  
  for (i = 0 ; i < searchStrLen ; i++)
    {
      backIndex[i] = 0;
      for (j = 1 ; j < i ; j++)
	if (strncmp (searchStr, searchStr + j, i - j) == 0)
	  backIndex[i] = i - j;
    }

  index = 0;
  counter = 0;

  while ((c = fgetc (fp)) != EOF)
    {
      if (c == searchStr[index])
	{
	  index++;
	  if (index == searchStrLen)
	    {
	      counter++;
	      index = 0;
	    }
	}
      else
	{
	  index = backIndex[index];
	  if (c == searchStr[index])
	    index++;
	  else
	    index = 0;
	}
    }
    free (backIndex);
  return counter;
}

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

  progName = argv[0];
  
  if (argc != 3)
    usage ();

  if ((fp = fopen (argv[2], "rb")) == NULL)
    error ("Can not open file.");

  printf ("%d\n", countString (fp, argv[1]));

  fclose (fp);
  return 0;
}
----------------------------------------

入力のバッファリングはプログラムが長くなるだけで、面白くないの
で省略しました。検索のアルゴリズムはちょっと変わってるかも。

	ＢＡＡ