2

假设我有以下内容:

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

如何使用 C 搜索dummydummy 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

在http://www-igm.univ-mlv.fr/~lecroq/string/上对大量字符串搜索算法进行了广泛的讨论,并附有说明性的 C 代码和参考资料。

一组评论中有关于算法成本的讨论。要记住的一点是,如果您可以通过多次调用搜索函数来分摊设置成本,那么高性能算法可以为您带来巨大的好处。如果您要一直搜索不同的字符串,则更难胜出。

我有一个版本的 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()等完成的环境中工作,并且您必须能够按需切换内存分配器。你可以忽略这两个 typedef 和对应的函数;当然,默认设置是使用malloc()free()

基本的 KMP 算法代码来自上面的站点 - 但经过修改以允许我设置一次搜索字符串,然后搜索多个目标字符串等。请联系我(请参阅我的个人资料)以获取源代码。我也有类似的 Boyer-Moore 代码结构(相同的原始来源),以及不区分大小写的 Boyer-Moore 代码。

strstr()在 Kernighan 和 Pike 的优秀著作《编程实践》中有一个很好的战争故事和表演。


我做了一些实验——使用 King James Bible (4.8 MB) 的副本作为纯文本,并对其进行内存映射。对于许多搜索,(MacOS X 10.6.2 / BSD)strstr()比 KMP 或 BM 都快。当字符串变得足够长(大约 12+ 个字符)时,BM 算法最终超过了strstr(). KMP 算法似乎总是慢得多

德?

  • 很难超越一个好的图书馆。
  • 在似是而非的英语语言字符串上,KMP 比 BM 慢得多。

而且我围绕算法设置的基础设施可能过于繁重 - 但原始代码中的替代方案是回调机制,它为确定匹配的上下文带来了一些问题。

于 2010-03-27T21:09:57.923 回答
2

如果你想要一些简单的东西并且你的字符串不是太长,你可以使用strstr函数。但是,如果您的字符串很长,请考虑使用KMP算法,因为它更有效。

我不太喜欢维基百科的文章,因为那里的实现对我来说有点奇怪(尽管它可能是正确的),而且它也误导了 KMP 的性能。我更喜欢这里给出的实现和描述,以及谷歌搜索“KMP 算法”返回的其他网站。

于 2010-03-27T20:13:20.973 回答
0

我自己一直很喜欢 Boyer-Moore。O(n),但必须设置(即,必须预先计算两个表。)因此,如果要搜索大量文本,或者预先知道搜索字符串,这样就可以弥补成本。建立表格。它也最适合 8 位 ASCII。

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

(顺便说一句,strstr() 有 Unicode 风格吗?)

于 2010-03-27T20:36:10.483 回答
0

我会使用strstr(也在这里)。

我不是关于在问题中使用“部分”一词。参数(“dummy”或“dummy text”)必须完全匹配,对吗?

于 2010-03-27T20:22:11.640 回答