如何在 C 中部分比较两个字符串？

StackOverflow https://stackoverflow.com/questions/2530751

  •  22-09-2019
  •  | 
  •  

题

假设我有以下内容：

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

我如何搜索 dummy 或者 dummy text 在那个字符串中使用C？有没有简单的方法可以做到这一点，或者只能通过强大的字符串操作来实现？我所需要的只是搜索它并返回一个带有结果的布尔值。

编辑：
你们围绕这个主题进行了一场大讨论，并提出了一些算法，我不介意，因为这可能对其他人有用，甚至将来对我有用。但我真正想要的是最简单的方法来做到这一点，无论时间/空间复杂度如何。这对我正在做的事情并不重要。所以， strstr 轻松快速地解决了我的问题。我真的必须给我一些标准的 C 函数记录表。

有帮助吗？

解决方案

这种情况的标准库函数是 的strstr：

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

它返回一个指针到字符串在找到匹配，或者NULL，如果它不是 - 所以，如果你需要的是一个布尔值，只是测试的返回值（if (strstr(...))

其他提示

在以下位置对大量字符串搜索算法进行了广泛的讨论： 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() 以及在克尼根和派克的优秀著作《编程实践".

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

德？

  • 很难超越一个好的图书馆。
  • 在看似合理的英语语言字符串上，KMP 比 BM 慢得多。

我围绕算法建立的基础设施可能太重了 - 但原始代码中的替代方案是回调机制，这在确定匹配上下文时带来了一些问题。

可以，如果你想要的东西简单使用 的strstr功能您的字符串不是太长。如果你的字符串很长但是，考虑 KMP 算法，因为它是很多更有效。

我真的不喜欢维基百科的文章，作为实现有一个有点怪在我看来（虽然它可能是正确的），并且它也带有误导性质的KMP的性能。我喜欢给定的此处和搜索由谷歌返回其他网站 “KMP算法”。

我一直很喜欢博耶 - 穆尔，我自己。这是O（n），但必须设置（即，两个表必须预先计算）。因此，它是很好的，如果大量的文本是要搜索或搜索字符串是事先知道，从而弥补了成本建设中的表。它也是最适合的8位ASCII。

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

（顺便说一句，在那里的的strstr一个Unicode味（）？）

我会用 斯特斯特 （还 这里).

我不想在问题中使用“部分”一词。参数（“虚拟”或“虚拟文本”）必须完全匹配，对吧？

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top