悩んでいる人
C言語で文字列の検索方法を教えて！
こういった悩みにお答えします．
本記事の信頼性
- リアルタイムシステムの研究歴12年．
- 東大教員の時に，英語でOS（Linuxカーネル）の授業．
- 2012年9月～2013年8月にアメリカのノースカロライナ大学チャペルヒル校（UNC）コンピュータサイエンス学部で客員研究員として勤務．C言語でリアルタイムLinuxの研究開発．
- プログラミング歴15年以上，習得している言語: C/C++，Python，Solidity/Vyper，Java，Ruby，Go，Rust，D，HTML/CSS/JS/PHP，MATLAB，Verse（UEFN）, Assembler (x64，aarch64)．
- 東大教員の時に，C++言語で開発した「LLVMコンパイラの拡張」，C言語で開発した独自のリアルタイムOS「Mcube Kernel」をGitHubにオープンソースとして公開．
- 2020年1月～現在はアメリカのノースカロライナ州チャペルヒルにあるGuarantee Happiness LLCのCTOとしてECサイト開発やWeb/SNSマーケティングの業務．2022年6月～現在はアメリカのノースカロライナ州チャペルヒルにあるJapanese Tar Heel, Inc.のCEO兼CTO．
- 最近は自然言語処理AIとイーサリアムに関する有益な情報発信や，Unreal Editor for Fortnite（UEFN）でゲーム開発に従事．
- （AI全般を含む）自然言語処理AIの論文の日本語訳や，AIチャットボット（ChatGPT，Auto-GPT，Gemini（旧Bard）など）の記事を50本以上執筆．アメリカのサンフランシスコ（広義のシリコンバレー）の会社でChatGPT/Geminiを訓練するプロンプトエンジニア・マネージャー・Quality Assurance（QA）の業務委託の経験あり．
- （スマートコントラクトのプログラミングを含む）イーサリアムや仮想通貨全般の記事を200本以上執筆．イギリスのロンドンの会社で仮想通貨の英語の記事を日本語に翻訳する業務委託の経験あり．
- UEFNで10本以上のゲームを開発し，フォートナイト上で公開（Fortnite，Fortnite.GG）．
こういった私から学べます．
C言語を独学で習得することは難しいです．
私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．
私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！
独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！
目次
C言語で文字列の検索
C言語で文字列の検索方法を紹介していきます．
文字列の検索とは，ある文字列の中に特定の部分文字列があるかどうか判定することです．
例えば，文字列"abcdbcde"の中に部分文字列"bc"はあると判定し，部分文字列"cb"はないと判定します．
まずは文字列中の文字を検索するstrchr/strrchr関数の使い方と自作関数を知りたいあなたはこちらからどうぞ．
strstr/strcasestr関数で文字列の検索
次に，文字列の中の部分文字列を検索する方法を紹介していきます．
|
1 2 |
char *strstr(const char *haystack, const char *needle); char *strcasestr(const char *haystack, const char *needle); |
strstr/strcasestr関数は，部分文字列の位置を発見する関数です．
strstr関数は，部分文字列needleが文字列 haystack中で最初に現れる位置を発見します．
strcasestr関数はstrstr関数と同様ですが，両方の引数に対して大文字小文字を無視します．
これらの関数は，見つかった部分文字列の開始を指すポインタを返します．
strstr/strcasestr関数の使い方
strstr/strcasestr関数の使い方は以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #define _GNU_SOURCE #include <stdio.h> #include <stdlib.h> #include <string.h> int main(int argc, char *argv[]) { char *p; if (argc != 3) { fprintf(stderr, "Usage: %s [str] [str2]\n", argv[0]); exit(1); } if ((p = strstr(argv[1], argv[2])) != NULL) { printf("strstr(): \"%s\" is found in \"%s\".\n", argv[2], argv[1]); printf("strstr(): s = %p, p = %p, pos = %ld\n", argv[1], p, p - argv[1]); } else { printf("strstr(): \"%s\" is not found in \"%s\".\n", argv[2], argv[1]); } if ((p = strcasestr(argv[1], argv[2])) != NULL) { printf("strcasestr(): \"%s\" is found in \"%s\".\n", argv[2], argv[1]); printf("strcasestr(): s = %p, p = %p, pos = %ld\n", argv[1], p, p - argv[1]); } else { printf("strcasestr(): \"%s\" is not found in \"%s\".\n", argv[2], argv[1]); } return 0; } |
文字列"abc"の中で部分文字列"bc"を検索する実行結果は以下になります．
strstr/strcasestr関数の両方とも発見できていることがわかります．
|
1 2 3 4 5 6 |
$ gcc strstr.c $ a.out abc bc strstr(): "bc" is found in "abc". strstr(): s = 0x7ffe750fceb8, p = 0x7ffe750fceb9, pos = 1 strcasestr(): "bc" is found in "abc". strcasestr(): s = 0x7ffe750fceb8, p = 0x7ffe750fceb9, pos = 1 |
文字列"abc"の中で部分文字列"BC"を検索する実行結果は以下になります．
strstr関数は発見できませんでしたが，strcasestr関数は発見できていることがわかります．
|
1 2 3 4 5 |
$ gcc strstr.c $ a.out abc BC strstr(): "BC" is not found in "abc". strcasestr(): "BC" is found in "abc". strcasestr(): s = 0x7ffcd08f7eb8, p = 0x7ffcd08f7eb9, pos = 1 |
文字列"abc"の中で部分文字列"de"を検索する実行結果は以下になります．
strstr/strcasestr関数の両方とも発見できなかったことがわかります．
|
1 2 3 4 |
$ gcc strstr.c $ a.out abc de strstr(): "de" is not found in "abc". strcasestr(): "de" is not found in "abc". |
strstr/strcasestr関数の自作
strstr/strcasestr関数の自作関数「mystrstr/mystrcasestr関数」のコードは以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdlib.h> #include <string.h> char *mystrstr(const char *haystack, const char *needle) { size_t l1, l2; if ((l2 = strlen(needle)) == 0) { return (char *) haystack; } l1 = strlen(haystack); while (l1 >= l2) { l1--; if (strncmp(haystack, needle, l2) == 0) { return (char *) haystack; } haystack++; } return NULL; } char *mystrcasestr(const char *haystack, const char *needle) { size_t l1, l2; if ((l2 = strlen(needle)) == 0) { return (char *) haystack; } l1 = strlen(haystack); while (l1 >= l2) { l1--; if (strncasecmp(haystack, needle, l2) == 0) { return (char *) haystack; } haystack++; } return NULL; } int main(int argc, char *argv[]) { char *p; if (argc != 3) { fprintf(stderr, "Usage: %s [str] [str2]\n", argv[0]); exit(1); } if ((p = mystrstr(argv[1], argv[2])) != NULL) { printf("mystrstr(): \"%s\" is found in \"%s\".\n", argv[2], argv[1]); printf("mystrstr(): s = %p, p = %p, pos = %ld\n", argv[1], p, p - argv[1]); } else { printf("mystrstr(): \"%s\" is not found in \"%s\".\n", argv[2], argv[1]); } if ((p = mystrcasestr(argv[1], argv[2])) != NULL) { printf("mystrcasestr(): \"%s\" is found in \"%s\".\n", argv[2], argv[1]); printf("mystrcasestr(): s = %p, p = %p, pos = %ld\n", argv[1], p, p - argv[1]); } else { printf("mystrcasestr(): \"%s\" is not found in \"%s\".\n", argv[2], argv[1]); } return 0; } |
実行結果は以下になります．同様です．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
$ gcc mystrstr.c $ a.out abc bc mystrstr(): "bc" is found in "abc". mystrstr(): s = 0x7ffe0644ceb8, p = 0x7ffe0644ceb9, pos = 1 mystrcasestr(): "bc" is found in "abc". mystrcasestr(): s = 0x7ffe0644ceb8, p = 0x7ffe0644ceb9, pos = 1 $ a.out abc BC mystrstr(): "BC" is not found in "abc". mystrcasestr(): "BC" is found in "abc". mystrcasestr(): s = 0x7fff3d91aeb8, p = 0x7fff3d91aeb9, pos = 1 $ a.out abc de mystrstr(): "de" is not found in "abc". mystrcasestr(): "de" is not found in "abc". |
文字列検索アルゴリズム
文字列検索アルゴリズムを紹介していきます．
力任せ法（ナイーブ法）
力任せ法（ナイーブ法）は，文字列と部分文字列を先頭から1文字ずつ比較し，不一致の場合は部分文字列を1文字だけ右に移動します．
繰り返し部分文字列の先頭から1文字ずつ比較する処理を繰り返します．
ナイーブ法のコードは以下になります．
※先述したmystrstr関数の実装と同様です．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdlib.h> #include <string.h> char *naive(const char *haystack, const char *needle) { size_t l1, l2; if ((l2 = strlen(needle)) == 0) { return (char *) haystack; } l1 = strlen(haystack); while (l1 >= l2) { l1--; if (strncmp(haystack, needle, l2) == 0) { return (char *) haystack; } haystack++; } return NULL; } int main(int argc, char *argv[]) { char *p; if (argc != 3) { fprintf(stderr, "Usage: %s [str] [str2]\n", argv[0]); exit(1); } if ((p = naive(argv[1], argv[2])) != NULL) { printf("\"%s\" is found in \"%s\".\n", argv[2], argv[1]); printf("s = %p, p = %p, pos = %ld\n", argv[1], p, p - argv[1]); } else { printf("\"%s\" is not found in \"%s\".\n", argv[2], argv[1]); } return 0; } |
文字列"abc"の中で部分文字列"bc"を検索する実行結果は以下になります．
|
1 2 3 4 |
$ gcc naive.c $ a.out abc bc "bc" is found in "abc". s = 0x7ffcefb76eb8, p = 0x7ffcefb76eb9, pos = 1 |
クヌース・モリス・プラット法（KMP法）
クヌース・モリス・プラット法（KMP法）は，文字列から部分文字列を検索する際，不一致となった位置と部分文字列自身の情報（テーブル）から次に照合を試すべき位置を決定することで検索を効率化するアルゴリズムです．
KMP法のコードは以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdlib.h> #include <string.h> void print_table(int *table, size_t n) { size_t i; for (i = 0; i < n; i++) { printf("table[%zu] = %d\n", i, table[i]); } } void init_table(int *table, size_t n, const char *needle) { size_t i, j; table[0] = -1; i = 2; j = 0; if (n >= 2) { table[1] = 0; while (i < n) { if (needle[i - 1] == needle[j]) { table[i] = j + 1; i++; j++; } else if (j > 0) { j = table[j]; } else { table[i] = 0; i++; } } } } char *kmp(const char *haystack, const char *needle) { size_t l1, l2; size_t i, m; int *table; if ((l2 = strlen(needle)) == 0) { return (char *) haystack; } l1 = strlen(haystack); if ((table = malloc(sizeof(int) * l2)) == NULL) { fprintf(stderr, "Error: cannot allocate memory %zu bytes.\n", sizeof(int) * l2); exit(1); } init_table(table, l2, needle); print_table(table, l2); m = i = 0; while (m + i <= l1) { if (needle[i] == haystack[m + i]) { i++; if (i == l2) { free(table); return (char *) &haystack[m]; } } else { m = m + i - table[i]; if (i > 0) { i = table[i]; } } } free(table); return NULL; } int main(int argc, char *argv[]) { char *p; if (argc != 3) { fprintf(stderr, "Usage: %s [str] [str2]\n", argv[0]); exit(1); } if ((p = kmp(argv[1], argv[2])) != NULL) { printf("\"%s\" is found in \"%s\".\n", argv[2], argv[1]); printf("s = %p, p = %p, pos = %ld\n", argv[1], p, p - argv[1]); } else { printf("\"%s\" is not found in \"%s\".\n", argv[2], argv[1]); } return 0; } |
実行結果は以下になります．
|
1 2 3 4 5 6 |
$ gcc kmp.c $ a.out abc bc table[0] = -1 table[1] = 0 "bc" is found in "abc". s = 0x7fffbacd2eb8, p = 0x7fffbacd2eb9, pos = 1 |
ボイヤー・ムーア法（BM法）
ボイヤー・ムーア法（BM法）は，KMP法と同様に文字列から部分文字列を検索する際，不一致となった位置と部分文字列自身の情報（テーブル）から次に照合を試すべき位置を決定することで検索を効率化するアルゴリズムです．
KMP法とは異なり，BM法は部分文字列の末尾から先頭に向けて検索します．
BM法は最良と最悪で大きく計算量が異なり，KMP法は最良でも最悪でも線形時間で検索が完了します．
つまり，BM法は計算時間の分散が大きく，KMP法は計算時間の分散が小さい傾向にあります．
BM法のコードは以下になります．
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 |
/* * Author: Hiroyuki Chishiro * License: 2-Clause BSD */ #include <stdio.h> #include <stdlib.h> #include <string.h> #define TABLE_SIZE 256 void print_table(int *table, size_t n) { size_t i; for (i = 0; i < n; i++) { if (table[i] != n) { printf("table[%zu] = %d\n", i, table[i]); } } } void init_table(int *table, const char *needle, size_t n) { int cnt = 0; for (cnt = 0; cnt < TABLE_SIZE; cnt++) { table[cnt] = n; } for (cnt = 0; cnt < n; cnt++) { table[(size_t)needle[cnt]] = n - cnt - 1; } } char *bm(const char *haystack, const char *needle) { size_t l1, l2; int i, j; int table[TABLE_SIZE]; if ((l2 = strlen(needle)) == 0) { return (char *) haystack; } l1 = strlen(haystack); init_table(table, needle, l2); #if PDEBUG print_table(table, TABLE_SIZE); #endif i = j = l2 - 1; while (i < l1 && j >= 0) { if (haystack[i] != needle[j]) { if (table[(int)haystack[i]] > l2 - j) { i += table[(int)haystack[i]]; } else { i += l2 - j; } j = l2 - 1; } else { i--; j--; } } if (j < 0) { return (char *) &haystack[i + 1]; } return NULL; } int main(int argc, char *argv[]) { char *p; if (argc != 3) { fprintf(stderr, "Usage: %s [str] [str2]\n", argv[0]); exit(1); } if ((p = bm(argv[1], argv[2])) != NULL) { printf("\"%s\" is found in \"%s\".\n", argv[2], argv[1]); printf("s = %p, p = %p, pos = %ld\n", argv[1], p, p - argv[1]); } else { printf("\"%s\" is not found in \"%s\".\n", argv[2], argv[1]); } return 0; } |
実行結果は以下になります．
※print_table関数でtableの内容を表示したい場合，GCCのコンパイルオプションに「-DPDEBUG」を付けて下さい．
|
1 2 3 4 |
$ gcc bm.c $ a.out abc bc "bc" is found in "abc". s = 0x7fff974d1eb8, p = 0x7fff974d1eb9, pos = 1 |
まとめ
C言語で文字列の検索方法（strstr関数）とナイーブ法，KMP法，BM法を紹介しました．
文字列の検索方法はC言語の課題でよく出てきますので，きちんと理解しておきましょう．
他の文字列検索アルゴリズムに興味があるあなたは以下の記事がおすすめです．
C言語で正規表現を利用した文字列の検索方法を知りたいあなたはこちらからどうぞ．
C言語を独学で習得することは難しいです．
私にC言語の無料相談をしたいあなたは，公式LINE「ChishiroのC言語」の友だち追加をお願い致します．
私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！
独学が難しいあなたは，元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう．後悔はさせません！
