Cでstrstr()関数を実装する(反復および再帰的)
Cでstrstr関数を実装するための効率的なプログラムを作成します strstr() 関数は、別の文字列で最初に出現する文字列へのポインタを返します。
のプロトタイプ strstr() は：
const char* strstr(const char* X, const char* Y);
1.反復実装
以下は、の反復実装です strstr() 関数。の最初の出現へのポインタを返します Y の X またはnullポインタの場合 Y の一部ではありません X。このソリューションの時間計算量は O(m.n) どこ m と n それぞれ文字列XとYの長さです。
|
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 |
#include <stdio.h> //`X`と`Y`が同じ場合はtrueを返します int compare(const char *X, const char *Y) { while (*X && *Y) { if (*X != *Y) { return 0; } X++; Y++; } return (*Y == '\0'); } // `strstr()`関数を実装する関数 const char* strstr(const char* X, const char* Y) { while (*X != '\0') { if ((*X == *Y) && compare(X, Y)) { return X; } X++; } return NULL; } //Cで`strstr()`関数を実装します int main() { char *X = "Techie Delight - Ace the Technical Interviews"; char *Y = "Ace"; printf("%s\n", strstr(X, Y)); return 0; } |
出力:
Ace the Technical Interviews
2.使用する memcmp() 関数
以下は strstr を使用した実装 memcmp() コードで定義された関数。このソリューションの時間計算量は変わりません O(m.n).
|
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 |
#include <stdio.h> // `strstr()`関数を実装する関数 const char *strstr(const char *X, const char *Y) { size_t n = strlen(Y); while (*X) { if (!memcmp(X, Y, n)) { return X; } X++; } return 0; } //Cで`strstr()`関数を実装します int main() { char *X = "Techie Delight – Ace the Technical Interviews"; char *Y = "Ace"; printf("%s\n", strstr(X, Y)); return 0; } |
出力:
Ace the Technical Interviews
3. KMPアルゴリズムの使用(効率的)
使用することもできます KMPアルゴリズム この問題を解決するために O(m + n) 複雑さ、ここで m と n 文字列の長さです X と Y、 それぞれ。
|
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 |
#include <stdio.h> //KMPアルゴリズムを使用して`strstr()`関数を実装する関数 const char* strstr(const char* X, const char* Y, int m, int n) { //基本ケース1：`Y`はNULLまたは空です if (*Y == '\0' || n == 0) { return X; } //基本ケース2： `X`がNULLであるか、Xの長さがYの長さよりも短い if (*X == '\0' || n > m) { return NULL; } // `next[i]`は、次に最適な部分一致のインデックスを格納します int next[n + 1]; for (int i = 0; i < n + 1; i++) { next[i] = 0; } for (int i = 1; i < n; i++) { int j = next[i + 1]; while (j > 0 && Y[j] != Y[i]) { j = next[j]; } if (j > 0 || Y[j] == Y[i]) { next[i + 1] = j + 1; } } for (int i = 0, j = 0; i < m; i++) { if (*(X + i) == *(Y + j)) { if (++j == n) { return (X + i - j + 1); } } else if (j > 0) { j = next[j]; i--; //`i`は次の反復でインクリメントされるため } } return NULL; } //Cで`strstr()`関数を実装します int main(void) { char *X = "Techie Delight – Ace the Technical Interviews"; char *Y = "Ace"; printf("%s\n", strstr(X, Y, strlen(X), strlen(Y))); return 0; } |
出力:
Ace the Technical Interviews
以上です strstr() Cでの実装。
こちらも参照: