Форум АНТИЧАТ

Форум АНТИЧАТ (https://forum.antichat.xyz/index.php)
-   С/С++, C#, Delphi, .NET, Asm (https://forum.antichat.xyz/forumdisplay.php?f=24)
-   -   проблема с буферами Part 3 (https://forum.antichat.xyz/showthread.php?t=96930)

fire64 18.12.2008 17:21
проблема с буферами Part 3
 
есть два буфера нужно определить входит ли первый буфер в состав второго

что-то типа этого

PHP код:
#include <stdlib.h>
#include <string.h>


void main ()
{


char *a = "aaagggbbb"

char *b = "ggg";



int n = проверить( b, a );


} 
какие функции есть в C, что бы это выполнить

izlesa 18.12.2008 17:30
char *strstr(char *, char *)
Ищет первое вхождение одной строки в другой и возвращает указатель на него. А вообще почитай что-нибудь про стандартную библиотеку. MSDN тотже.

Delimiter 18.12.2008 18:54
2 izlesa

справдедиво лишь для буферов хранящих строки! Хотя все равно не понятно .... а сравнивать ли символы после 0x00. To do or not to do! What is the question!


в общем же случае ... вычисляется хэш равный сумме малого буфера
ХЭШ=Сумма(b[i])
.... вычислетя хэш "плавающего" фрагмента большого буфера
ХЭШ2=Сумма_фрагмента(a[i])
и пусть buf_length - длинна большого буфера
а buf2_length -длина малого буфера

тогда ...далее

Код:
int find_inside(char *a,char *b,int buf_length,int buf2_length)
{
int i,j,ex;
long ХЭШ,ХЭШ2;
for(j=0,ХЭШ=0,ХЭШ2=0;j<buf2_length;j++)
{  ХЭШ+=b[j];    ХЭШ2+=a[j]; }

for(i=0,ex=-1;i<buf_length-buf2_length && ex==-1;i++,ХЭШ2=ХЭШ2-a[i-1]+a[i+buf2_length])
{
  if(ХЭШ==ХЭШ2)
    if(memcmp(a+i,b,buf2_len)==0)
      ex=i;
}
return ex;
}
если возвращает -1 не было совпадений если >-1 то это отступ от начала буфера

суть должна быть понятна... технология быстрого поиска подстроки в строке, но на манер буферов! 8))


СУПЕР-быстродействие ! Быстрее не получится!

P.S. это к разговору давнишнему (применение олимпиадных технологий в жизни) !

izlesa 18.12.2008 21:12
2Delimiter
Ну в вопросе присутствовали строки ).
Но алгоритм хорош ^______^

St0nX 19.12.2008 15:17
Код:
int FindStr(char *str1,char *str2)
{
        int nstr1,nstr2,i,j,nstr,sstr;
        nstr1=strlen(str1);
        nstr2=strlen(str2);
        if(nstr1>nstr2)
        {
                nstr=nstr1-nstr2;
                for(i=0;i<nstr;i++)
                {
                        sstr=0;
                        for(j=0;j<nstr2;j++)
                        {
                                if(str1[j+i]==str2[j])
                                {
                                        sstr++;
                                }
                        }
                        if(sstr==nstr2)
                        {
                                return 1;
                        }
                }
        }
                else
                {
                        return -1;
                }
                return 0;
}
Не уверен как будет работать strlen с 0х00 ну при необходимости можно и переписать


Время: 10:47