Как я могу частично сравнить две строки в C?

Question

Скажем, у меня есть следующее содержание:

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

Как искать dummy или dummy text в этой строке, используя C? Есть ли простой способ сделать это или только при сильных манипуляциях с строкой? Все, что мне нужно - это искать его и возвращать логическое значение с результатом.

EDIT:
Вы, ребята создали большую дискуссию вокруг этой темы и предложил несколько алгоритмов, и я не против того, что причина этого может быть полезным для кого-то еще, или даже меня в будущем. Но то, что я действительно хотел, было самым простым способом сделать это, независимо от сложности времени и пространства. Это не имеет большого значения для того, что я делаю. Итак, strstr легко и быстро исправил мою проблему. Мне действительно нужно получить мне стандартный набор функций CH.

Answer 1

Стандартная библиотека функций для этого strstr:

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

возвращает указатель на строку, где матч был найден, или NULL, если оно не было - так что, если все, что вам нужно, это логическое значение, просто проверить возвращаемое значение (if (strstr(...)).

Answer 2

вы можете использовать функцию strstr, если вы хотите что-то простое и ваши строки не слишком долго. Если ваши строки очень долго, однако, рассмотрим алгоритм KMP, так как это намного больше

Мне не очень нравится статья в Википедии, так как реализация выглядит немного странно для меня (хотя это, вероятно, правильно), и это также вводит в заблуждение о производительности KMP. Я предпочитаю реализацию и описание, данное here, а также на других сайтах, которые были возвращены поиском Google для «алгоритма KMP».

Answer 3

Я бы использовал strstr (также here).

Я не говорю об использовании слова «частичный» в вопросе. Аргумент («фиктивный» или «фиктивный текст») должен быть полностью согласован, не так ли?

Answer 4

Мне всегда нравился Бойер-Мур. Это O (n), но должно быть настроено (т. Е. Две таблицы должны быть предварительно вычислены.) Таким образом, хорошо, если много текста нужно искать, или строки поиска известны заранее, что компенсирует стоимость построения таблиц. Он также подходит для 8-битного ASCII.

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

(Кстати, есть вкус Юникод strstr()?)

Answer 5

Там в обширном обсуждение большого числа алгоритмов строкового поиска по 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() и так далее, и вы должны быть в состоянии для переключения распределителя памяти по требованию. Вы можете игнорировать два typedefs и соответствующую функцию; по умолчанию, конечно, использовать malloc() и free().

Основной код алгоритма KMP приведен с сайта выше, но был изменен, чтобы я мог задать строку поиска один раз, а затем выполнить поиск нескольких целевых строк и т. Д. Свяжитесь со мной (см. Мой профиль) для исходного кода. У меня есть аналогичная структура для кода Бойер-Мура тоже (тот же исходный источник), а также нечувствительный к регистру код Бойер-Мура.

Есть хорошая история войны о strstr() и исполнении в отличной книге Кернигана и Пайка «The Practice of Programming».

---

Я сделал некоторые эксперименты - используя копию Библии короля Джеймса (4,8 MB) как обычный текст, и память отображения этого. Для многих поисков (MacOS X 10.6.2/BSD) strstr() был быстрее, чем KMP или BM. Когда строки росли достаточно долго (примерно 12+ символов), тогда алгоритм BM, наконец, опережал strstr(). Алгоритм KMP всегда казался намного медленнее.

Мораль?

• Трудно выйти из хорошей библиотеки.
• KMP намного медленнее BM на правдоподобных строках английского языка.

И инфраструктура, которую я устанавливаю вокруг алгоритмов, может быть слишком тяжелой, но альтернатива в исходном коде является механизмом обратного вызова, что создает некоторые проблемы для определения контекста совпадений.