ページ 11

文字列から文字列を探索

Posted: 2016年7月21日(木) 14:16
by けろけろ

コード:

#include <stdio.h>
int main(void) {
	int a, b, c, x, i;
	char moji[]="ABCDEFG HIJKLMN OPQRSTU VWXYZ";
	char retsu[10];

	printf("%sy\n",moji);
	printf("探索する文字列(10文字以内)を入力:");
	scanf("%s", retsu);

	


	return 0;
}



打ち込んだ文字列が
最初の文字列にあるかどうかを探索するプログラムは
この先どうしたらいいのですか?

Re: 文字列から文字列を探索

Posted: 2016年7月21日(木) 15:59
by みけCAT
strstrかなんかを使って実装したらいいと思いますが、まず「最初の文字列」とはなんですか?
オフトピック
メッセージには「10文字以内」とありますが、10文字(10バイト)入力すると最後のヌル文字が範囲外に書き込まれ、未定義動作を起こすので、
このプログラムには10バイト以上(10バイトを含みます、念のため)の文字列を入力してはいけません。
(これは文字列として入力するデータが9バイトを超えるとダメということです。例えば9バイト+改行文字の合計10バイト、というのはOK)

Re: 文字列から文字列を探索

Posted: 2016年7月21日(木) 16:10
by けろけろ
みけCAT さんが書きました:strstrかなんかを使って実装したらいいと思いますが、まず「最初の文字列」とはなんですか?
オフトピック
メッセージには「10文字以内」とありますが、10文字(10バイト)入力すると最後のヌル文字が範囲外に書き込まれ、未定義動作を起こすので、
このプログラムには10バイト以上(10バイトを含みます、念のため)の文字列を入力してはいけません。
(これは文字列として入力するデータが9バイトを超えるとダメということです。例えば9バイト+改行文字の合計10バイト、というのはOK)

税所の文字列というのは、
ABCD~
とかのやつです!

あと、strstrを使わずにやる方法を知りたいです!

Re: 文字列から文字列を探索

Posted: 2016年7月21日(木) 16:24
by みけCAT
けろけろ さんが書きました:あと、strstrを使わずにやる方法を知りたいです!
Boyer Moore法かなんかを使って実装すればいいでしょう。

Re: 文字列から文字列を探索

Posted: 2016年7月21日(木) 17:38
by けろけろ
みけCAT さんが書きました:
けろけろ さんが書きました:あと、strstrを使わずにやる方法を知りたいです!
Boyer Moore法かなんかを使って実装すればいいでしょう。

探索のアルゴリズムや、繰り返し、分岐をつかってできませんか?

Re: 文字列から文字列を探索

Posted: 2016年7月21日(木) 17:45
by みけCAT
けろけろ さんが書きました:探索のアルゴリズムや、繰り返し、分岐をつかってできませんか?
Boyer Moore法は探索のアルゴリズムの一種です。
繰り返しや分岐も使います。
従って、できるはずです。

Re: 文字列から文字列を探索

Posted: 2016年7月21日(木) 18:41
by けろけろ
みけCAT さんが書きました:
けろけろ さんが書きました:探索のアルゴリズムや、繰り返し、分岐をつかってできませんか?
Boyer Moore法は探索のアルゴリズムの一種です。
繰り返しや分岐も使います。
従って、できるはずです。

まだそれは学習していなくて・・・
リニアサーチや、番兵や、バイナリサーチを使いたいです

Re: 文字列から文字列を探索

Posted: 2016年7月21日(木) 18:59
by usao
何に困っているのかがわかりません.


例えば,
「長さ5文字の文字列 "ABCDE" の中に,
 長さ3文字の文字列 "CDE" が含まれているかどうかを調べる」
みたいなことをするのだろうと想像しますが,

"ABCDE"の一部である"ABC" は "CDE" と同一か?
"ABCDE"の一部である"BCD" は "CDE" と同一か?
"ABCDE"の一部である"CDE" は "CDE" と同一か?

のように,何の工夫もなく
"ABCDE"の先頭側から順に調べていくのでは都合が悪いのですか?

Re: 文字列から文字列を探索

Posted: 2016年7月21日(木) 19:09
by けろけろ
usao さんが書きました:何に困っているのかがわかりません.


例えば,
「長さ5文字の文字列 "ABCDE" の中に,
 長さ3文字の文字列 "CDE" が含まれているかどうかを調べる」
みたいなことをするのだろうと想像しますが,

"ABCDE"の一部である"ABC" は "CDE" と同一か?
"ABCDE"の一部である"BCD" は "CDE" と同一か?
"ABCDE"の一部である"CDE" は "CDE" と同一か?

のように,何の工夫もなく
"ABCDE"の先頭側から順に調べていくのでは都合が悪いのですか?


どうやるのですか??

Re: 文字列から文字列を探索

Posted: 2016年7月21日(木) 22:14
by box
けろけろ さんが書きました: どうやるのですか??
くだんの例ならば、探したい文字列"CDE"は3文字なので、
探されたい文字列"ABCDE"について、
1)0~2文字目の3文字を取得する。"ABC"を取得できる。"CDE"とは等しくない。
2)1~3文字目の3文字を取得する。"BCD"を取得できる。"CDE"とは等しくない。
3)2~4文字目の3文字を取得する。"CDE"を取得できる。"CDE"と等しい。探索終了。
てな具合に、探されたい文字列のすべて(今回だと0~4文字目)をすべてカバーできるような
繰り返しを実行すれば、見つかるか見つからないかのいずれかがわかるはずです。

Re: 文字列から文字列を探索

Posted: 2016年7月22日(金) 02:16
by かずま
けろけろ さんが書きました:
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;
}
strstr を使ってはいけないのはなぜですか?
strlen, strchr, strncmp も使ってはいけないのですか?

strstr を使ったら書けるのですか?
書けるのなら、ここに提示してください。