C言語-#7.str*str

はおはお。

strstr関数は文字列から指定した文字列があるかチェックする関数です。ここでは先に公開した比較関数を使用して実装します。

strnstr

char* strnstr(const char* s, const char* ptn, int ptnlen) {
  int ch1 = *ptn;                   // 最初の文字
  int ch2 = *(ptn + (ptnlen - 1));  // 最後の文字

  int i;

  // s の長さチェック
  for (i = 0; i < ptnlen; ++i) {
    if (s[i] == '\0') {
      return 0;  // s が ptn よりも短い
    }
  }

  s = s + (ptnlen - 1);  // 位置を ptn 分進める

  for (;;) {
    // 最後と最初が一致
    if (*s == ch2 && *(s - (ptnlen - 1)) == ch1) {
      // ※最初と最後は判定済み
      if (strncmp(s - (ptnlen - 1) + 1, ptn + 1, ptnlen - 2) == 0) {
        return (char*)(s - (ptnlen - 1));
      }
    }
    // null がきたので終了
    else if (*s == '\0') {
      return 0;
    }

    ++s;
  }

  //return 0;
}

strnstr関数は s から長さ ptnlen が ptn列に見つかるまで走査します。
文字列を比較するときはパターンの先頭と終端を先に比較して一致していれば全体を比較します。少しでも比較回数を減らすためのちょっとした方法です。
strncmpの引数がややこしくなってますが、123456 とあった場合に 2345 を比較する式です。これはコメントにもありますが、すでに先頭と終端は比較済みだからです。
あと、(s - (ptnlen - 1)) はちょっと冗長かもですね。

strstr

char* strstr(const char* s, const char* ptn) {
  return strstrs, ptn, strlen(ptn));
}

パターンの長さを strnstr に渡すだけですね。

了

けっこー速度には自信あるんですけどどうなんでしょ。この関数を使って grepソフトを作成しました。古いソフトなのでちゃんと動くかな……。

ゆーぐれっぷの詳細情報 : Vector ソフトを探す！

おまけ strstr（BM法）

char* strstr(const char* s, const char* ptn)
{
	// 文字列 or パターンがあるときだけー
/*	if (!s && !ptn) {
		return -1; // 文字がないよー
	}
*/
	
	int s_len	= strlen(s);
	int ptn_len	= strlen(ptn);
	
	// テキストとパターンの不一致が見つかったときに
	// どれだけずらすかを示す表\_
	int skip[256];
	
	// 変数 i は注目しているテキストの位置、
	// 変数 j は注目しているパターンの位置を表すポインタ
	int	i, j;
	
	// テキストよりパターンのほうが長いので見つからないです
	if (s_len < ptn_len) {
		return 0;
	}
	
	// 表 skip を作成する
	for (i = 0; i < 256; ++i) {
		skip[i] = ptn_len;
	}
	for (i = 0; i < ptn_len - 1; ++i) {
		skip[(uint8_t)ptn[i]] = ptn_len - i - 1;
	}
	
	// ポインタを初期化する。パターンの後ろから前に向かって比較するので、
	// パターンの長さ -1 に初期化する。
	i = ptn_len - 1;
	
	// テキストの最後尾に行き当たるまで繰り返す
	while (i < s_len) {
		// ポインタ j をパターンの最後の文字を指すようにする
		j = ptn_len - 1;
		
		// テキストとパターンが一致する間、繰り返す
		while (s[i] == ptn[j]) {
			// 最初の文字まで一致したら、探索は成功である
			if (j == 0) {
				return s + i;
			}
			
			// ポインタ i と j をそれぞれ１文字分戻す
			i--;
			j--;
		}
		
		// 一致しなかったので、パターンをずらす
		if (skip[(uint8_t)s[i]] > (ptn_len - j)) {
			i += skip[(uint8_t)s[i]];
		}
		else {
			i += ptn_len - j;
		}
	}
	
	
	// 結局見つからなかった
	return 0;
}