Алгоритм поиска подстроки методом боера-мура на Visual с++, с паскаля на visual с++ Опции

[invoke]

я только не давно начал изучать visual с++ и уменя не получилось перевести алгоритм.... а тут задание по практике дали на с++ хоть вешайся сдавать в четвег а у меня не чего не получаеться так что есле кто поможет первести буду очень багодарен ......
а вот сам алгоритм Реализуем указанный алгоритм на языке ObjectPascal. Прежде всего следует определить тип данных «таблица смещений». Для кодовой таблицы, состоящей из 256 символов, определение этого типа будет выглядеть так:

type TBMTable = array [0..255] of Integer;



Далее приводится процедура, вычисляющая таблицу смещений для образца P.

procedure MakeBMTable( var BMT : TBMTable; const P : String);
var i : Integer;
begin
for i := 0 to 255 do BMT[i] := Length(P);
for i := Length(P) downto 1 do
if BMT[Byte(P[i])] = Length(P) then
BMT[Byte(P[i])] := Length(P) – i;end;



Теперь напишем функцию, осуществляющую поиск.

function BMSearch( StartPos : Integer; const S, P : String; const BMT : TBMTable) : Integer;
var Pos, lp, i : Integer;
begin lp := Length(P);
Pos := StartPos + lp –1;
while Pos < Length(S) do
if P[lp] <> S[Pos] then Pos := Pos + BMT[S[Pos]]
else
for i := lp - 1 downto 1 do
if P[i] <> S[Pos – lp + i] then
begin
Inc(Pos);
Break;
end
else if i = 1 then
begin
Result := Pos – lp + 1;
Exit;
end;
Result := 0;
end;

заранее спасибо.....

[volvo]

Странный вы народ... То с С++ на Паскаль просите перевести, то обратно...

Алгоритм Боуера-Мура. "c" -> "pascal"

[invoke]

а чего там такиу веселые функции которые не чего не возрашают PRE_GS и PRE_BC )))

[invoke]

/* Preprocessing */void CPraktukaDlg::PRE_KMP( char *x, int m, int kmp_next[] )
{ int i, j; i=0;
j=kmp_next[0]=-1;
while ( i < m )
{ while ( j > -1 && x[ i ] != x[ j ] ) j=kmp_next[ j ];
i++; j++;
if ( x[ i ] == x[ j ] ) kmp_next[i]=kmp_next[j];

else kmp_next[ i ] = j;
}}
void CPraktukaDlg::KMP( char *x, char *y, int n, int m )
{ int i, ii,j, kmp_next[100];
char f[100];
/* Preprocessing */
PRE_KMP(x, m, kmp_next );
/* Searching */
i=j=0;
while ( i < n )
{ while ( j > -1 && x[ j ] != y[ i ] ) j = kmp_next[ j ];
i++; MessageBox("out");
j++; if ( j >= m )
{ // OUTPUT( i - j);
ii=i-j;
MessageBox(itoa(ii,f,10) );
j = kmp_next[ j ];
} }
}
void CPraktukaDlg::OnButton1()
{
UpdateData(true);
char *s1,*s2;

s1=(char*)malloc(strlen(m_edit1));
s2=(char*)malloc(strlen(m_edit2));
for(int i=0;i<strlen(m_edit2);i++)
{
if(i<strlen(m_edit1))
s1[i]=m_edit1[i];
s2[i]=m_edit2[i];
}
if((strlen(m_edit2)>=strlen(m_edit1)) &&(strlen(m_edit1)!=0)&&(strlen(m_edit1)!=0))

KMP(s2,s1,strlen(m_edit2),strlen(m_edit1));
вот то что получилось но что то не работает может кто увидет ошибку напишите плз
и еще я так и не понял в чем смысл OUTPUT( i - j); она же всегда выводит 0 что.....

[volvo]

char* StrInStr(LPTSTR Str,LPTSTR SubStr)
{
int i,LenStr,LenSub,BMT[256];
BYTE *pos;

 LenSub=strlen(SubStr);
 if(LenSub<1) return NULL;
 LenStr=strlen(Str);
 if(LenStr<1) return NULL;

// Создаём таблицу
 for(i=0;i<256;i++) BMT[i]=LenSub;
 for(i=LenSub-1;i>=0;i--)
     if(BMT[(BYTE)*(SubStr+i)]==LenSub) BMT[(BYTE)*(SubStr+i)]=LenSub-1-i;

// Ищем
 pos=(BYTE*)Str+LenSub-1;
 while(pos<(BYTE*)(Str+LenStr)) {
       if((BYTE)*(SubStr+LenSub-1) != *pos) pos+=BMT[*pos];
       else for(i=LenSub-2;i>=0;i--) {
            if((BYTE)*(SubStr+i) != *(pos-(LenSub-1)+i)) {
                pos++;
                break;
            }
            else if(i==0) return(char*)(pos-LenSub+1);// Есть совпадение
       }
 }
// Совпадений нет
return NULL;
}

(С) DrUnkard

Проверяй, должно работать... В принципе, был вариант, работающий еще быстрее, но это уже не совсем Boyer-Moore...

[invoke]

спасибо сейчас посмотрю

[invoke]

так спасобо тебе огромное)))))))))))))))))))))))))))))))))))))))))))))))))))))))))
не много доработал и все отлично работает
вот код на
с++char* CPousk_podstrokuDlg::StrInStr(LPTSTR Str,LPTSTR SubStr)
{
int i,LenStr,LenSub,BMT[256];
BYTE *pos;

LenSub=strlen(SubStr);
if(LenSub<1) return NULL;
LenStr=strlen(Str);
if(LenStr<1) return NULL;
MessageBox("1");

for(i=0;i<256;i++) BMT[i]=LenSub;
for(i=LenSub-1;i>=0;i--)
if(BMT[(BYTE)*(SubStr+i)]==LenSub) BMT[(BYTE)*(SubStr+i)]=LenSub-1-i;
MessageBox("2");

pos=(BYTE*)Str+LenSub-1;
while(pos<(BYTE*)(Str+LenStr))
{ if((BYTE)*(SubStr+LenSub-1) != *pos) pos+=BMT[*pos];
else for(i=LenSub-2;i>=0;i--)
{ if((BYTE)*(SubStr+i) != *(pos-(LenSub-1)+i))
{ pos++;
break;
}
else if(i==0) return(char*)(pos-LenSub+1);
MessageBox("est sovpadenue");
}
}
MessageBox("netttttttttt sovpadenue");
return NULL;
}
void CPousk_podstrokuDlg::OnButton1()
{
char *s1,*s2;
s1=(char*)malloc(strlen(m_edit1));
s2=(char*)malloc(strlen(m_edit2));
for(int i=0;i<strlen(m_edit2);i++)
{
if(i<strlen(m_edit1))
s1[i]=m_edit1[i];
s2[i]=m_edit2[i];
}

StrInStr(s2,s1);
+ к ето тому надо добавить с++char* CPousk_podstrokuDlg::StrInStr(LPTSTR Str,LPTSTR SubStr);
вот ету строчку надо написать в фаил название_проекта_dlg.h и все ето описываем public))))
volvo Респект спасибо за алгоритм
вот так что тут все