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

Автор: Neon6868 10.03.2007 19:59

Надо написать программу, которая осуществляет поиск подстроки в строке 2 методами(прямой поиск в строке и алгоритм Боуера и Мура). Для каждого метода определить число сравнений, за которые строка будет найдена или не найдена.Каждый из этих методов реализовать с помощью процедур.В основной программе запрашивактся ввод имени текстового файла, затем запрашивается ввод подстроки поиска.Затем организуется цикл пока файл не кончится, в котором считывается строка, затем идёт поочереди обращение к одной процедуре и к другой.Процедуре передать считанную из файла строку, подстроку, переменные, которые будут счётчиками сравнений.Потом когда цикл кончится на экран выводится в какой строке обнаружена подстрока, с какой позиции в строке она начинается и за сколько сравнений была обнаружена.Если не обнаружена, то вывести соответствующее сообщение и за сколько сравнений.

Файл в самом низу

Я прогу написал, но она не всегда правильно считает:

1. Если подстроки нет в тексте, то прога неправильно считает число сравнений.
2. Прога не всегда правильно считает число сравнений для некоторых слов.Например, слово crimes в самом конце текста.
3. Если взять текст с программой на Паскале, то прога, если написать сразу 2 слова, вообще считает всё неправильно.

Вот прога:

Program Stroka;
    var
    z,a,k,i,j,y:integer;
    t:text;
    name,st,st2:string[80];
    key1,key2:boolean;
Procedure poisk1(var i,y:integer;st,st2:string);
    var
    j:integer;
    m,n:byte;
   Begin
    m:=ord(st2[0]);
    n:=ord(st[0]);
    i:=-1;
    y:=-1;
    repeat
    i:=i+1;
    j:=1;
    while (j<=m) and (st[i+j]=st2[j]) do
   begin
    y:=y+1;
    j:=j+1;
   end;
    y:=y+1;
    until (j=m+1) or (i=n-m);
    if j=m+1 then i:=i+1;
    if (j<>m+1) and (i=n-m) then i:=0;
End;
Procedure poisk2(var k,z:integer;st,st2:string);
    var
    m,n:byte;
    d:array[char] of byte;
    i,x:integer;
   Begin
    m:=ord(st2[0]);
    n:=ord(st[0]);
    for i:=0 to 255 do d[chr(i)]:=m;
    for j:=1 to m-1 do d[st2[j]]:=m-j;
    i:=m;
    j:=m;
    z:=-1;
    while (j>0) and (i<=n) do
   begin
    j:=m;
    k:=i;
    z:=z+1;
    while (j>0) and (st[k]=st2[j]) do
   begin
    k:=k-1;
    j:=j-1;
    z:=z+1;
   end;
    i:=i+d[st[i]];
   end;
    if j<>0 then k:=0;
End;
   Begin
    writeln('Vvedite imya faila:');
    readln(name);
    assign(t,name);
    reset(t);
    a:=0;
    writeln;
    writeln('Vvedite podstroky poiska:');
    read(st2);
    readln;
    writeln('Tekst:');
    while not eof(t) and ((i=0) and (k=0)) do
   begin
    readln(t,st);
    a:=a+1;
    write(st);
    writeln;
    poisk1(i,y,st,st2);
    poisk2(k,z,st,st2);
    end;
    if (i<>0) or (k<>0) then
   begin
    writeln;
    writeln('Pryamoi poisk:');
    write('Nomer stroki:',a);
    writeln;
    write('Nomer pozicii podstroki v stroke:',i);
    writeln;
    writeln('Chislo sravnenii v stroke:',y);
    writeln('Algoritm Bouera i Mura:');
    write('Nomer stroki:',a);
    writeln;
    write('Nomer pozicii podstroki v stroke:',k+1);
    writeln;
    writeln('Chislo sravnenii v stroke:',z);
   end;
   if (i=0) and (k=0) then
   begin
    writeln('Podstroka ne obnaruzhena!');
    writeln('Pryamoi poisk:');
    write('Chislo sravnenii v stroke:',y);
    writeln;
    writeln('Algoritm Bouera i Mura:');
    writeln('Chislo sravnenii v stroke:',z);
   end;
    close(t);
    readln;
End.

файл:

more, the operations of our businesses, governments, 
and financial institutions are controlled by information
that exists only inside computer memories. Anyone 
clever enough to modify this information for his own 
purposes can reap substantial rewards.Even worse, a 
number of people who have done this and been caught 
at it have managed to get away without punishment. 
These facts have not been lost on criminals or would-be 
criminals. A  recent Stanford Research Institute study of
computer abuse was based on 160 case histories, which 
probably are just the proverbial tip of the iceberg. After 
all, we only know about the unsuccessful crimes

Автор: volvo 10.03.2007 22:46

Сам написал? А зачем? Что, нормальной реализации, приведенной в FAQ-е было недостаточно?

А вот отсюда - поподробнее:
ГДЕ ты в приведенном тобой тексте видишь слово crimes? Покажи а то у меня видно со зрением проблемы - НЕ ВИЖУ Я ЕГО! А если его нет - о чем речь в п. 2?

P.S. Пока не будет НОРМАЛЬНОГО критерия, что считать словами - ответа не будет... Что именно ты ищещь в программе на Паскале? Приводи свои тесты ПОЛНОСТЬЮ, а не так, как ты привел - только когнстатацию фактов: дублировать уже проделанную тобой работу желания нет совершенно...

Автор: Neon6868 11.03.2007 0:46

А где в FAQе ты видел эту программу, а то я не могу найти???

Извини я случайно удалил слово crimes!



Надо искать подстроку в строке. Например,когда я ищу слово crimes, он неправильно считает число сравнений.А если набрать любые буквы на клавиатуре, которых нет в тексте, то программа также неправильно считает число сравнений!!!!!

Автор: Neon6868 11.03.2007 17:44

Неужели никто не знает в чём ошибки???

Автор: Neon6868 12.03.2007 21:51

Всем спасибо. Помощь больше не нужна!