C言語関係掲示板

過去ログ

No８７９　文字列1の後ろから文字列2を探す

[戻る]　[ホームページ]
No.11396
文字列
投稿者---rei(2003/12/22 14:11:28)


いきづまっています。教えてください。

長さ　n の文字列txt の中に、長さk の文字列pat がどこにあるか
を調べる関数を定義しなさい。文字列　pat が複数ある場合は
最後にあらわれるpat の位置を見つけること。

また、その関数を利用して、任意行数のテキストファイルの中に
文字列が最後に現れる位置（何行目、何文字目）を出力する
プログラムを作りなさい。ファイル名と文字列の指定方法は、
コマンド行引数、標準入力など、自分の好きな方法を使ってよい。

No.11397
Re:文字列
投稿者---shu(2003/12/22 14:27:46)
http://park6.wakwak.com/~nougaki/


この関数を自作するのかな？

http://www9.plala.or.jp/sgwr-t/lib/strstr.html
No.11398
Re:文字列
投稿者---rei(2003/12/22 14:52:52)


>この関数を自作するのかな？
>
>http://www9.plala.or.jp/sgwr-t/lib/strstr.html

多分そうだと思います。私はポインタがあまりよく理解していないので、力任せ法（単純法)で作っている最中です。
No.11400
Re:文字列
投稿者---YuO(2003/12/22 15:47:41)


>この関数を自作するのかな？
>http://www9.plala.or.jp/sgwr-t/lib/strstr.html

ちょっと違うようです。

>>長さ　n の文字列txt の中に、長さk の文字列pat がどこにあるか
>>を調べる関数を定義しなさい。文字列　pat が複数ある場合は
>>最後にあらわれるpat の位置を見つけること。

なので，終端がナル文字でないようですし，最後に見つかるものを探すそうですから。
＃引用中の強調は私が付け加えました。

nが巨大でないなら，後ろから力任せに探すのが一番簡単な気がします。
BM法とか使ってもいいですが……。
No.11402
Re:文字列
投稿者---shu(2003/12/22 17:18:51)
http://park6.wakwak.com/~nougaki/


>nが巨大でないなら，後ろから力任せに探すのが一番簡単な気がします。

力任せに作ってみました。

>BM法とか使ってもいいですが……。

http://alfin.mine.utsunomiya-u.ac.jp/~niy/algo/
の20でも見てみます。

000: #include <stdio.h>
001: #include <string.h>
002: 
003: int searchString( const char* txt, const char* pat );
004: 
005: int main( void )
006: {
007:     char txt[] = "abcdefghijklmnopqrstuvwxyz";
008:     char pat[] = "hijklmn";
009:     
010:     printf("%d", searchString( txt, pat ));
011:     
012:     return 0;
013: }
014: 
015: int searchString( const char* txt, const char* pat )
016: {
017:     int n = strlen(txt);
018:     int k = strlen(pat);
019:     static int pos;
020:     
021:     for (pos = n - k; pos > 0; pos--) {
022:         if (!strncmp((txt + pos), pat, k))
023:             break;
024:     }
025:     
026:     return pos;
027: }
028:

No.11405
Re:文字列
投稿者---YuO(2003/12/22 17:59:53)		 


019:     static int pos;


posをstaticにする必要性がないです。

関数内のstaticは，「関数の状態を内部で持っている」ことを意味します。
この関数は完結しますから，外部から見た場合に状態を持ちません。
staticを付けることは，他人に対してposの役割や関数についてミスリードさせる可能性を秘めています。


021:     for (pos = n - k; pos > 0; pos--) {
022:         if (!strncmp((txt + pos), pat, k))
023:             break;
024:     }


このループでは，先頭のみが一致する場合に検出できません。
for (pos = n - k + 1; pos > 0; pos--) {
    if (!memcmp(txt + pos - 1, pat, k)) break;
}

のように，1だけ減ずる必要があります。
No.11412
Re:文字列
投稿者---おでん(2003/12/22 20:21:30)


>nが巨大でないなら，後ろから力任せに探すのが一番簡単な気がします。
>BM法とか使ってもいいですが……。

力任せの前から探索です (@_@)。
もし文字列が通常の('\0'で終る)文字列ならば・・・ですが。

const char * rSubStr( const char* txt, const char* pat )
{
    const char * ptr= txt ;
    const char * old= NULL ; /* 一個前 */

    while((ptr= strstr(ptr,pat)) != NULL ){
        old= ptr ;
        ptr++ ;
    }

    return old;
}