第1回文字列比較（4月10日）

□ 来週のために（兼，出席代わりに）

1. /home/tokuhisa/lect3/member/ に 学籍番号をファイル名として，
   「学籍番号 漢字氏名 半角ローマ字名 半角ローマ字性 住所 生年月日 メールアドレス」
   を書いたファイルを置く．以上は，半角スペースにより区切ること．
   ただし，学籍番号は半角数字のみ，漢字氏名および住所はスペースを入れない，半角ローマ字氏名はスペースを入れる，生年月日の年は西暦，月と日は2桁になるように0を入れる．
   （例） 992036 山田太郎 Taro Yamada 鳥取県鳥取市湖山町南 19800410 ytaro@ike.tottori-u.ac.jp
   なお，住所と生年月日はデタラメでも良い．

   chmod 666 ファイル名 を実行する．

   以上を授業が終了する前までに済ませておくこと．

□ コンパイル方法

警告を表示するオプション

gcc -Wall hogehoge.c

■ 文字列の格納

⇒ トレース1

⇒ list0100.c

• char型の配列変数に1つずつ文字を代入，最後に'\0'を代入 list0101.c
• char へのポインタ変数を，ローカルの定数に割り当て list0102.c
• char へのポインタ変数を，動的に確保したメモリ域に1つずつ文字を代入，最後に'\0'を代入 list0103.c

悪い例 list0104.c （ローカルの定数は，該当スコープ内のみ有効）

■ 文字列のコピー

例題１：	文字列s2を領域s1に高々size文字までをコピーするサブルーチン「void mystrncpy(char *s1, const char *s2, int size)」を作成せよ．
	s1 の領域はサブルーチンが呼ばれる前に確保されているものとする．s2の終端に至る前に size ぶんだけコピーをすると終了する．size ぶんだけコピーをする前に，s2の終端がある場合は，終端をコピーし，直ちに終了する．
	返り値はない．
	※ 組み込み関数 strncpy と若干仕様が異なる．

• 答え
  ⇒ list0105.c

■ 文字列の完全一致

課題１：	2つの文字列を比較するサブルーチン「int mystrcmp(const char *s1, const char *s2)」を作成せよ．
	返り値は，s1 が s2 よりも小さいならば，負の整数値，等しいならば 0，大きいならば正の整数値とする．
	プログラムファイル名 ⇒ prac0101.c



• 文字列 *s1 と *s2 の比較アルゴリズム
  1. *s1 と *s2 が一致している間以下を繰り返す
     1. もし *s1 が終端コードであるならば，0 を返す
     2. そうでなければ，s1 と s2 のポインタを進める
  2. *s1 と *s2 の文字コードの差分を返す
• 注意点
  • 文字コードは euc を使う．⇒ コード一覧
  • euc コードは 2 バイトで 1 文字を表す．たとえば， s1[0]=0xa4, s1[1]=0xa2, s1[0]='\0' のとき 「 printf("%s",s1)」とすると「あ」が表示される．
  • 0xff は正の値として扱うこと
• テストプログラム
  一致サブルーチンを「int mystrcmp(const char *, const char *)」とする
  ⇒ list0106.c

■ 包含する文字列の検査

課題２：	部分文字列の位置を探すサブルーチン「char *mystrstr(const char *s1, const char *s2)」を作成せよ．
	返り値は，部分文字列の開始を指すポインタを返す．もし，部分文字列が見つからないならば NULL を返す．
	プログラムファイル名 ⇒ prac0102.c



• 文字列 *s1 から文字列 *s2 の存在位置を探すアルゴリズム
  1. *s1 が終端コードでない間以下を繰り返す
     1. s1 を b1 に，s2 を b2 に，代入する
     2. *b1 と *b2 が等しい間以下を繰り返す
        1. もし，*b1 が終端コードであるならば，s1 を返す．
        2. b1 と b2 のポインタを進める．
     3. もし，*b2 が終端コードであるならば，s1 を返す．
     4. s1 のポインタを進める．
  2. NULL を返す．
• ⇒ トレース2
• テストプログラム
  一致サブルーチンを「char *mystrstr(const char *, const char *)」とする
  ⇒ list0107.c

課題３：	簡易BM法による部分文字列探索サブルーチン「char *mystrstr(const char *s1, const char *s2)」を作成せよ．
	返り値は，部分文字列の開始を指すポインタを返す．もし，部分文字列が見つからないならば NULL を返す．
	プログラムファイル名 ⇒ prac0103.c

• スキップ幅の計算方法 ⇒ トレース3
  1. スキップ幅は，文字ごとに決まるので，あらかじめ計算し，int skip[256] というテーブルに格納
  2. 検索キーの文字列に含まれない文字Xは，検索キーの文字列長lenをスキップ値とする．（例．skip[X] = len）
  3. 検索キーの文字列のうち i 番目に含まれる文字ならば，len - i - 1 をスキップ値とする．ただし，検索キー文字列に同じ文字が複数出現する場合は，最後に出現した位置を i としてスキップ値を計算する．
  ⇒ PAD図
  ※ 配列変数の番号に char 型の変数値を用いる場合は， unsigned char によりキャストを行うこと
  

  探索のメイン ⇒ トレース4

  1. 文字列 s1 の長さを len1，文字列 s2 の長さを len2 とする．
  2. 文字列s1の先頭と文字列s2の先頭を並べ，s2の最後尾に対応するs1の位置を t1 とする．（要するに t1 = len2 - 1）
  3. t1 が len1 未満である間，以下を繰り返す．
     1. s2 の最後尾を t2 とする．（要するに t2 = len2 - 1）
     2. t1 の指す s1 上の文字と t2 の指す s2 上の文字が一致する間，以下を繰り返す．
        1. もし，t2 が s2 の先頭の文字を指すならば，t1 の指す s1 の文字のポインタ値を返す．
        2. t1 と t2 をそれぞれ1つ減らす．
     3. t1 の指す s1 上の文字に依り skip テーブルを参照し，その値だけ t1 を進める．
  4. NULL を返す．

  mystrstr関数では，基本的には，スキップ幅の計算の後，探索メインの処理を行う．しかし，正しく動作するためには幾つかの追加が必要．