文字列から文字列を探索
Posted: 2016年7月21日(木) 14:16
みけCAT さんが書きました:strstrかなんかを使って実装したらいいと思いますが、まず「最初の文字列」とはなんですか?オフトピックメッセージには「10文字以内」とありますが、10文字(10バイト)入力すると最後のヌル文字が範囲外に書き込まれ、未定義動作を起こすので、
このプログラムには10バイト以上(10バイトを含みます、念のため)の文字列を入力してはいけません。
(これは文字列として入力するデータが9バイトを超えるとダメということです。例えば9バイト+改行文字の合計10バイト、というのはOK)
Boyer Moore法かなんかを使って実装すればいいでしょう。けろけろ さんが書きました:あと、strstrを使わずにやる方法を知りたいです!
みけCAT さんが書きました:Boyer Moore法かなんかを使って実装すればいいでしょう。けろけろ さんが書きました:あと、strstrを使わずにやる方法を知りたいです!
Boyer Moore法は探索のアルゴリズムの一種です。けろけろ さんが書きました:探索のアルゴリズムや、繰り返し、分岐をつかってできませんか?
みけCAT さんが書きました:Boyer Moore法は探索のアルゴリズムの一種です。けろけろ さんが書きました:探索のアルゴリズムや、繰り返し、分岐をつかってできませんか?
繰り返しや分岐も使います。
従って、できるはずです。
usao さんが書きました:何に困っているのかがわかりません.
例えば,
「長さ5文字の文字列 "ABCDE" の中に,
長さ3文字の文字列 "CDE" が含まれているかどうかを調べる」
みたいなことをするのだろうと想像しますが,
"ABCDE"の一部である"ABC" は "CDE" と同一か?
"ABCDE"の一部である"BCD" は "CDE" と同一か?
"ABCDE"の一部である"CDE" は "CDE" と同一か?
のように,何の工夫もなく
"ABCDE"の先頭側から順に調べていくのでは都合が悪いのですか?
くだんの例ならば、探したい文字列"CDE"は3文字なので、けろけろ さんが書きました: どうやるのですか??
けろけろ さんが書きました:どうやるのですか??usao さんが書きました: 例えば,
「長さ5文字の文字列 "ABCDE" の中に,
長さ3文字の文字列 "CDE" が含まれているかどうかを調べる」
みたいなことをするのだろうと想像しますが,
"ABCDE"の一部である"ABC" は "CDE" と同一か?
"ABCDE"の一部である"BCD" は "CDE" と同一か?
"ABCDE"の一部である"CDE" は "CDE" と同一か?
のように,何の工夫もなく
"ABCDE"の先頭側から順に調べていくのでは都合が悪いのですか?
#include <stdio.h>
int match(char *a, char *b)
{
int j;
for (j = 0; j < 3; j++)
if (a[0+j] != b[j]) break;
if (j == 3) return 1;
for (j = 0; j < 3; j++)
if (a[1+j] != b[j]) break;
if (j == 3) return 1;
for (j = 0; j < 3; j++)
if (a[2+j] != b[j]) break;
if (j == 3) return 1;
return 0;
}
int main(void)
{
char a[] = "ABCDE", b[] = "CDE";
if (match(a, b))
puts("found");
else
puts("not found");
return 0;
}
#include <stdio.h>
int match(char *a, char *b)
{
int i, j;
for (i = 0; i <= 5 - 3; i++) {
for (j = 0; j < 3; j++)
if (a[i+j] != b[j]) break;
if (j == 3) return 1;
}
return 0;
}