Версия для печати темы

Автор: invoke 19.12.2006 23:44

я только не давно начал изучать 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 20.12.2006 0:03

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

http://forum.pascal.net.ru/index.php?s=&showtopic=3392&view=findpost&p=30494

Автор: invoke 20.12.2006 0:33

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

Автор: invoke 21.12.2006 0:54

/* 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 21.12.2006 1:05

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 21.12.2006 1:40

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

Автор: invoke 21.12.2006 2:35

так спасобо тебе огромное)))))))))))))))))))))))))))))))))))))))))))))))))))))))))
не много доработал и все отлично работает
вот код на
с++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 Респект спасибо за алгоритм
вот так что тут все

Автор: furosemide nursing consideration 23.09.2021 17:55

Buy Metformin Online

Автор: how do i know if lasix is workin 1.11.2021 8:56

Cephalexin Std

Автор: nishaknapp 29.07.2022 17:36

Why not settling on games that is fun and at the same time your earning. Well itll make suspense because of the game as well but dude just try it and it gave me hope while pandemic is real rn. https://www.z-news.xyz/online-gambling-is-going-all-in-worth-it/