IPB
ЛогинПароль:

> Внимание!

1. Пользуйтесь тегами кода. - [code] ... [/code]
2. Точно указывайте язык, название и версию компилятора (интерпретатора).
3. Название темы должно быть информативным.
В описании темы указываем язык!!!

Наладить общение поможет, если вы подпишитесь по почте на новые темы в этом форуме.

 
 Ответить  Открыть новую тему 
> Алгоритм поиска подстроки методом боера-мура на Visual с++, с паскаля на visual с++
сообщение
Сообщение #1





Группа: Пользователи
Сообщений: 5
Пол: Мужской
Реальное имя: Санек

Репутация: -  0  +


я только не давно начал изучать visual с++ и уменя не получилось перевести алгоритм.... unsure.gif а тут задание по практике дали на с++ хоть вешайся сдавать в четвег а у меня не чего не получаеться так что есле кто поможет первести буду очень багодарен smile.gif ......
а вот сам алгоритм Реализуем указанный алгоритм на языке 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;

заранее спасибо..... smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гость






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

Алгоритм Боуера-Мура. "c" -> "pascal"
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3





Группа: Пользователи
Сообщений: 5
Пол: Мужской
Реальное имя: Санек

Репутация: -  0  +


а чего там такиу веселые функции которые не чего не возрашают PRE_GS и PRE_BC ))) blink.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4





Группа: Пользователи
Сообщений: 5
Пол: Мужской
Реальное имя: Санек

Репутация: -  0  +


/* 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 что.....
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Гость






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...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6





Группа: Пользователи
Сообщений: 5
Пол: Мужской
Реальное имя: Санек

Репутация: -  0  +


спасибо сейчас посмотрю smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7





Группа: Пользователи
Сообщений: 5
Пол: Мужской
Реальное имя: Санек

Репутация: -  0  +


так спасобо тебе огромное))))))))))))))))))))))))))))))))))))))))))))))))))))))))) good.gif good.gif good.gif good.gif good.gif good.gif
не много доработал и все отлично работает
вот код на
с++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 Респект спасибо за алгоритм
вот так что тут все
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 28.10.2020 18:48
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name