2

次のコンテンツがあるとしましょう。

Lorem Ipsum is simply dummy text of the printing and typesetting industry.

Cを使用してその文字列を検索dummyまたは検索するにはどうすればよいですか？dummy textそれを行う簡単な方法はありますか、それとも強力な文字列操作だけで行う方法はありますか？必要なのは、それを検索して、結果とともにブール値を返すことだけです。

編集：
皆さんはこのトピックについて大きな議論を作成し、いくつかのアルゴリズムを提案しました。これが他の誰か、または将来私にさえ役立つかもしれないことを私は気にしません。しかし、私が本当に望んでいたのは、時間/空間の複雑さに関係なく、それを行うための最も簡単な方法でした。それは私がしていることには本当に関係ありません。だから、strstr簡単かつ迅速に私の問題を修正しました。私は本当にいくつかの標準的なC関数の虎の巻を手に入れなければなりません。

4

5 に答える 5

6

このための標準ライブラリ関数はstrstrです：

char *strstr(const char *haystack, const char *needle);

一致が見つかった文字列へのポインタを返します。一致しなかった場合はNULLを返します。したがって、必要なのがブール値だけの場合は、戻り値（if (strstr(...))。

于 2010-03-27T20:10:13.260 に答える
2

単純なものが必要で、文字列が長すぎない場合は、 strstr関数を使用できます。ただし、文字列が非常に長い場合は、KMPアルゴリズムの方がはるかに効率的であると考えてください。

ウィキペディアの記事はあまり好きではありません。実装が少し奇妙に見え（おそらく正しいとはいえ）、KMPのパフォーマンスについても誤解を招く可能性があります。私はここと「KMPアルゴリズム」のグーグル検索によって返された他のサイトで与えられた実装と説明を好みます。

于 2010-03-27T20:13:20.973 に答える
2

http://www-igm.univ-mlv.fr/~lecroq/string/には、多数の文字列検索アルゴリズムに関する広範な説明があり、Cコードとリファレンスが示されています。

アルゴリズムのコストについてのコメントのセットで議論があります。覚えておくべきポイントの1つは、検索関数の多くの呼び出しでセットアップのコストを償却できれば、高性能アルゴリズムが大きなメリットをもたらす可能性があるということです。常にさまざまな文字列を検索する場合、勝つことは困難です。

同じ検索文字列を複数回再利用するためにパッケージ化されたバージョンのKMP（Knuth-Morris-Pratt）アルゴリズムがあります。ヘッダーは次のとおりです。

/*
@(#)File:           $RCSfile: kmp.h,v $
@(#)Version:        $Revision: 1.4 $
@(#)Last changed:   $Date: 2008/02/02 05:49:34 $
@(#)Purpose:        Knuth-Morris-Pratt Search Algorithm
@(#)Author:         J Leffler
@(#)Copyright:      (C) JLSS 2005,2008
@(#)Product:        :PRODUCT:
*/

#ifndef KMP_H
#define KMP_H

#include <stddef.h> /* size_t */

typedef struct kmp_control kmp_control;

/*
** To set up a search (to repeatedly look for the same search string in
** multiple scan strings), use kmp_setsearch().  To start a search on a
** new scan string, use kmp_settarget().  To find the next match of a
** given search string in a given target string, use kmp_search().  Note
** that kmp_setsearch() and kmp_settarget() do not copy the data in the
** source and target strings; the pointers must remain valid You can
** copy kmp_control structures for reuse if desired.
*/
typedef void *(*kmp_malloc)(size_t nbytes);
typedef void (*kmp_free)(void *data);

extern kmp_control *kmp_setsearch(const char *search, size_t schlen);
extern void kmp_settarget(kmp_control *ctrl, const char *target, size_t tgtlen);
extern const char *kmp_search(kmp_control *ctrl);
extern void kmp_release(kmp_control *ctrl);
extern void kmp_setalloc(kmp_malloc mem_alloc, kmp_free mem_free);

#endif /* KMP_H */

メモリ割り当て関数を指定できるのは少し珍しいことですが、私のコードは、メモリ割り当てが標準malloc()などで行われない環境で機能することが多く、必要に応じてメモリアロケータを切り替えることができる必要があります。2つのtypedefと対応する関数は無視してかまいません。もちろん、デフォルト設定はとを使用malloc()しfree()ます。

基本的なKMPアルゴリズムコードは上記のサイトからのものですが、検索文字列を一度設定してから複数のターゲット文字列などを検索できるように変更されました。ソースコードについては私に連絡してください（私のプロファイルを参照）。ボイヤームーアコード（同じ元のソース）にも同様の構造があり、大文字と小文字を区別しないボイヤームーアコードもあります。

strstr()カーニハンとパイクの優れた本「プログラミング作法」には、優れた戦争物語とパフォーマンスがあります。

私はいくつかの実験を行いました-プレーンテキストとして欽定訳聖書（4.8 MB）のコピーを使用し、それをメモリマッピングしました。多くの検索では、（MacOS X 10.6.2 / BSD）strstr()はKMPまたはBMよりも高速でした。文字列が十分に長くなると（約12文字以上）、BMアルゴリズムは最終的にペースを上回りstrstr()ました。KMPアルゴリズムは常にはるかに遅いように見えました。

道徳？

  • 優れたライブラリを追い越すことは困難です。
  • KMPは、もっともらしい英語の文字列ではBMよりもはるかに低速です。

また、アルゴリズムの周りに配置したインフラストラクチャは重すぎる可能性がありますが、元のコードの代替手段はコールバックメカニズムであり、一致のコンテキストを決定するためのいくつかの問題があります。

于 2010-03-27T21:09:57.923 に答える
0

私はいつもボイヤームーア文字が好きでした。O（n）ですが、設定する必要があります（つまり、2つのテーブルを事前に計算する必要があります）。したがって、大量のテキストを検索する場合、または検索文字列を事前に知っている場合は、コストを補うのに適しています。テーブルを構築するのです。8ビットASCIIにも最適です。

[ http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm]

（ところで、strstr（）のUnicodeフレーバーはありますか？）

于 2010-03-27T20:36:10.483 に答える
0

私はstrstrを使用します（これもここにあります）。

私は質問で「部分的」という言葉を使用することについてではありません。引数（「ダミー」または「ダミーテキスト」）は完全に一致している必要がありますよね？

于 2010-03-27T20:22:11.640 に答える