C LANGUAGE TECHNOLOGY

【C言語】文字列をstrstr関数で検索【ナイーブ法,KMP法,BM法】

悩んでいる人

C言語で文字列の検索方法を教えて!

こういった悩みにお答えします.

本記事の信頼性

  • リアルタイムシステムの研究歴12年.
  • 東大教員の時に,英語でOSの授業.
  • 2012年9月~2013年8月にアメリカのノースカロライナ大学チャペルヒル校コンピュータサイエンス学部2021年の世界大学学術ランキングで20位)で客員研究員として勤務.C言語でリアルタイムLinuxの研究開発
  • プログラミング歴15年以上,習得している言語: C/C++Solidity,Java,Python,Ruby,HTML/CSS/JS/PHP,MATLAB,Assembler (x64,ARM).
  • 東大教員の時に,C++言語で開発した「LLVMコンパイラの拡張」,C言語で開発した独自のリアルタイムOS「Mcube Kernel」GitHubにオープンソースとして公開

こういった私から学べます.

C言語で文字列の検索

C言語で文字列の検索方法を紹介していきます.

文字列の検索とは,ある文字列の中に特定の部分文字列があるかどうか判定することです.

例えば,文字列"abcdbcde"の中に部分文字列"bc"はあると判定し,部分文字列"cb"はないと判定します.

strchr/strrchr関数で文字の検索

まず,文字列の中の文字を検索する方法を紹介していきます.

strchr/strrchr関数は,文字列中の文字の位置を特定する関数です.

strchr関数は文字列s中に最初に文字cが現れた位置へのポインタ,strrchr関数は文字列s中に最後に文字cが現れた位置へのポインタを返します.

strchr/strrchr関数の使い方

strchr/strrchr関数の使い方は以下になります.

文字列"abcdbcde"の中に文字'b'を発見した場合の実行結果は以下になります.

場所はpos = 0が先頭文字としてstrchr関数ではpos = 1,strrchr関数ではpos = 4の場所にあります.

文字列"abcdbcde"の中に文字'z'を発見できなかった場合の実行結果は以下になります.

strchr/strrchr関数の自作

strchr/strrchr関数の自作関数「mystrchr/mystrrchr関数」のコードは以下になります.

文字列"abcdbcde"の中に文字'b'を発見した場合の実行結果は以下になります.同様です.

文字列"abcdbcde"の中に文字'z'を発見できなかった場合の実行結果は以下になります.同様です.

strstr/strcasestr関数で文字列の検索

次に,文字列の中の部分文字列を検索する方法を紹介していきます.

strstr/strcasestr関数は,部分文字列の位置を発見する関数です.

strstr関数は,部分文字列needleが文字列 haystack中で最初に現れる位置を発見します.

strcasestr関数はstrstr関数と同様ですが,両方の引数に対して大文字小文字を無視します.

これらの関数は,見つかった部分文字列の開始を指すポインタを返します.

strstr/strcasestr関数の使い方

strstr/strcasestr関数の使い方は以下になります.

文字列"abc"の中で部分文字列"bc"を検索する実行結果は以下になります.

strstr/strcasestr関数の両方とも発見できていることがわかります.

文字列"abc"の中で部分文字列"BC"を検索する実行結果は以下になります.

strstr関数は発見できませんでしたが,strcasestr関数は発見できていることがわかります.

文字列"abc"の中で部分文字列"de"を検索する実行結果は以下になります.

strstr/strcasestr関数の両方とも発見できなかったことがわかります.

strstr/strcasestr関数の自作

strstr/strcasestr関数の自作関数「mystrstr/mystrcasestr関数」のコードは以下になります.

実行結果は以下になります.同様です.

文字列検索アルゴリズム

文字列検索アルゴリズムを紹介していきます.

力任せ法(ナイーブ法)

力任せ法(ナイーブ法)は,文字列と部分文字列を先頭から1文字ずつ比較し,不一致の場合は部分文字列を1文字だけ右に移動します.

繰り返し部分文字列の先頭から1文字ずつ比較する処理を繰り返します.

ナイーブ法のコードは以下になります.

※先述したmystrstr関数の実装と同様です.

文字列"abc"の中で部分文字列"bc"を検索する実行結果は以下になります.

クヌース・モリス・プラット法(KMP法)

クヌース・モリス・プラット法(KMP法)は,文字列から部分文字列を検索する際,不一致となった位置と部分文字列自身の情報(テーブル)から次に照合を試すべき位置を決定することで検索を効率化するアルゴリズムです.

KMP法のコードは以下になります.

実行結果は以下になります.

ボイヤー・ムーア法(BM法)

ボイヤー・ムーア法(BM法)は,KMP法と同様に文字列から部分文字列を検索する際,不一致となった位置と部分文字列自身の情報(テーブル)から次に照合を試すべき位置を決定することで検索を効率化するアルゴリズムです.

KMP法とは異なり,BM法は部分文字列の末尾から先頭に向けて検索します.

BM法は最良と最悪で大きく計算量が異なり,KMP法は最良でも最悪でも線形時間で検索が完了します.

つまり,BM法は計算時間の分散が大きく,KMP法は計算時間の分散が小さい傾向にあります.

BM法のコードは以下になります.

実行結果は以下になります.

※print_table関数でtableの内容を表示したい場合,GCCのコンパイルオプションに「-DPDEBUG」を付けて下さい.

まとめ

C言語で文字列の検索方法(strstr関数)とナイーブ法,KMP法,BM法を紹介しました.

文字列の検索方法はC言語の課題でよく出てきますので,きちんと理解しておきましょう.

他の文字列検索アルゴリズムに興味があるあなたは以下の記事がおすすめです.

C言語で正規表現を利用した文字列の検索方法を知りたいあなたはこちらからどうぞ.

C言語 正規表現
【C言語】regcomp/regexec/regerror/regfree関数で正規表現の検索【grep/sed/awkコマンドでも紹介】

こういった悩みにお答えします. こういった私から学べます. 目次1 正規表現2 C言語のregcomp/regexec/regerror/regfree関数で正規表現の検索3 参考:grep/sed/ ...

続きを見る

C言語を独学で習得することは難しいです.

私にC言語の無料相談をしたいあなたは,公式LINE「ChishiroのC言語」の友だち追加をお願い致します.

友だち追加

独学が難しいあなたは,C言語を学べるおすすめのオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう.後悔はさせません!

-C LANGUAGE, TECHNOLOGY
-, , , , , , , , ,