Re: Поиск строки в блоке памяти
От: zaufi Земля  
Дата: 03.08.11 09:08
Оценка: 2 (1)
Здравствуйте, zaichatki, Вы писали:

Z>Здравствуйте,


Z>Что-то не соображу как проще всего найти строку в блоке памяти (char*).

Z>strstr не подходит поскольку блок не единая строка и не нуль-терминированный (известен размер).
Z>Пока сделал на memchr + memcmp, ничего похожего на memstr что-то не нагугливавется. Может быть хотя бы под Windows есть что-нибудь?

потому что она называется memmem()
Re: Поиск строки в блоке памяти
От: c-smile Канада http://terrainformatica.com
Дата: 07.08.11 17:02
Оценка: 2 (1)
Здравствуйте, zaichatki, Вы писали:

Z>Что-то не соображу как проще всего найти строку в блоке памяти (char*).

Z>strstr не подходит поскольку блок не единая строка и не нуль-терминированный (известен размер).
Z>Пока сделал на memchr + memcmp, ничего похожего на memstr что-то не нагугливавется. Может быть хотя бы под Windows есть что-нибудь?


/*
Binary data search using Boyer-Moore algorithm, modified by R. Nigel Horspool  
see:
  http://www-igm.univ-mlv.fr/~lecroq/string/node18.html
SYNOPSIS:
   where - source data, src_length - source data byte length (bytes) 
   what - data to be sought, what_length - sought data length (bytes)
RETURNS: 
   address of 'what' data in 'where' block or 0 if not found.
   c adjustment was made by: andrew at terrainformatica.com 
*/
const void *mem_lookup(const void *where, size_t where_length, const void *what, size_t what_length )
{
#define WHAT ((const byte*)what) 
 
 int m1 = int(what_length) - 1;
 
 /* Preprocessing */
 int i,bm_bc[ 256 ];
 for ( i = 0; i < 256; i++ ) bm_bc[i] = int(what_length);
 for ( i = 0; i < m1; i++ ) bm_bc[ WHAT[i] ] = m1 - i;

 /* Searching */
 byte b, lastb = WHAT[ m1 ];

 const byte *p = (const byte *)where;
 const byte *end = p + where_length - what_length;
 for(; p <= end; p += bm_bc[ b ] ) 
 {
    b = p[ m1 ];
    if ( (b == lastb) && ( memcmp( p, what, m1 ) == 0 ) )
      return p;
 }
#undef WHAT
 return 0;
}
Поиск строки в блоке памяти
От: zaichatki  
Дата: 03.08.11 08:59
Оценка:
Здравствуйте,

Что-то не соображу как проще всего найти строку в блоке памяти (char*).
strstr не подходит поскольку блок не единая строка и не нуль-терминированный (известен размер).
Пока сделал на memchr + memcmp, ничего похожего на memstr что-то не нагугливавется. Может быть хотя бы под Windows есть что-нибудь?
Re: Поиск строки в блоке памяти
От: jazzer Россия Skype: enerjazzer
Дата: 03.08.11 09:15
Оценка:
Здравствуйте, zaichatki, Вы писали:

Z>Здравствуйте,


Z>Что-то не соображу как проще всего найти строку в блоке памяти (char*).

Z>strstr не подходит поскольку блок не единая строка и не нуль-терминированный (известен размер).
Z>Пока сделал на memchr + memcmp, ничего похожего на memstr что-то не нагугливавется. Может быть хотя бы под Windows есть что-нибудь?

Если нужно чисто С++-решение:

std::search( mem_begin, mem_end, str_begin, str_end );

jazzer (Skype: enerjazzer) Ночная тема для RSDN
Автор: jazzer
Дата: 26.11.09

You will always get what you always got
  If you always do  what you always did
Re: Поиск строки в блоке памяти
От: abdab Россия  
Дата: 03.08.11 09:19
Оценка:
Здравствуйте, zaichatki, Вы писали:

Можно реализовать свой strnstr через strncmp, например, как здесь
Re[2]: Поиск строки в блоке памяти
От: abdab Россия  
Дата: 03.08.11 09:21
Оценка:
Здравствуйте, zaufi, Вы писали:

Z>потому что она называется memmem()


Ее же вроде нет в стандартной библиотеке.
Re: Поиск строки в блоке памяти
От: ilnar Россия  
Дата: 03.08.11 09:21
Оценка:
Здравствуйте, zaichatki, Вы писали:

Z>Здравствуйте,


Z>Что-то не соображу как проще всего найти строку в блоке памяти (char*).

Z>strstr не подходит поскольку блок не единая строка и не нуль-терминированный (известен размер).
Z>Пока сделал на memchr + memcmp, ничего похожего на memstr что-то не нагугливавется. Может быть хотя бы под Windows есть что-нибудь?

возьмите код для strstr, уберите там проверки ноль символа и дополните параметрами размеров блоков
Re[2]: Поиск строки в блоке памяти
От: abdab Россия  
Дата: 03.08.11 09:24
Оценка:
Здравствуйте, abdab, Вы писали:

A>Здравствуйте, zaichatki, Вы писали:


A>Можно реализовать свой strnstr через strncmp, например, как здесь


Тема кстати поднималась здесь
Автор:
Дата: 25.09.05
, вроде автора ответы удовлетворили
Re[3]: Поиск строки в блоке памяти
От: zaufi Земля  
Дата: 03.08.11 09:33
Оценка:
Здравствуйте, abdab, Вы писали:

A>Здравствуйте, zaufi, Вы писали:


Z>>потому что она называется memmem()


A>Ее же вроде нет в стандартной библиотеке.


ну в общем да )

NAME
memmem — locate a substring

SYNOPSIS
#define _GNU_SOURCE /* See feature_test_macros(7) */
#include <string.h>

void *memmem(const void *haystack, size_t haystacklen,
const void *needle, size_t needlelen);

DESCRIPTION
The memmem() function finds the start of the first occurrence of the substring needle of length needlelen in the memory area
haystack of length haystacklen.

RETURN VALUE
The memmem() function returns a pointer to the beginning of the substring, or NULL if the substring is not found.

CONFORMING TO
This function is a GNU extension.

Re[2]: Поиск строки в блоке памяти
От: zaichatki  
Дата: 03.08.11 09:36
Оценка:
Здравствуйте, zaufi, Вы писали:

Z>потому что она называется memmem()


Да, ступил. Жаль под вин нет. С другой стороны, реализация там довольно прямолинейная. У меня сейчас практически также, только вместо цикла memchr.
Re[3]: Поиск строки в блоке памяти
От: zaufi Земля  
Дата: 03.08.11 09:49
Оценка:
Здравствуйте, zaichatki, Вы писали:

Z>Здравствуйте, zaufi, Вы писали:


Z>>потому что она называется memmem()


Z>Да, ступил. Жаль под вин нет. С другой стороны, реализация там довольно прямолинейная. У меня сейчас практически также, только вместо цикла memchr.


ну если хочется сложностей смотри сюда %)

или тут вот еще пачка с визуализацией работы на java appletах
Re[4]: Поиск строки в блоке памяти
От: zaichatki  
Дата: 03.08.11 09:58
Оценка:
Здравствуйте, zaufi, Вы писали:

Z>ну если хочется сложностей смотри сюда %)


Я наоборот перестал расстраиваться что у меня всё так просто раз уж в линуксовых либах также.
Re[5]: Поиск строки в блоке памяти
От: zaufi Земля  
Дата: 03.08.11 10:27
Оценка:
Здравствуйте, zaichatki, Вы писали:

Z>Здравствуйте, zaufi, Вы писали:


Z>>ну если хочется сложностей смотри сюда %)


Z>Я наоборот перестал расстраиваться что у меня всё так просто раз уж в линуксовых либах также.


посмотрел в исходники glibc 2.13-r4 (моя текущая), и боюсь разочарую тебя, но там все уже далеко не так просто

/* We use the Two-Way string matching algorithm, which guarantees
linear complexity with constant space. Additionally, for long
needles, we also use a bad character shift table similar to the
Boyer-Moore algorithm to achieve improved (potentially sub-linear)
performance.

See http://www-igm.univ-mlv.fr/~lecroq/string/node26.html#SECTION00260
and http://en.wikipedia.org/wiki/Boyer-Moore_string_search_algorithm
*/

 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.