Консультация № 180185
06.10.2010, 22:02
43.65 руб.
0 7 1
И снова добрый вечер, эксперты.
Помогите в написании программы на Delphi.
Задание такое:
Написать программу поиска Рабина. В Richedit занести текст, а в Edit искомую букву или слово. Найденный символ или слово выделить, а его координаты отобразить в Memo в виде: Строка 1: 13, 17 (где 13 и 17 номер искомого символа).

Обсуждение

Неизвестный
07.10.2010, 09:30
общий
это ответ
Здравствуйте, Kreaman.
Предлагаю Вам следующий вариант решения.
Код и описание в приложении.
Вопросы пишите в форум.
Удачи.

Добавил код с алгоритмом Рабина-Карпа.

Приложение:
unit Unit1;

interface

uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, ComCtrls;

type
TForm1 = class(TForm)
RichEdit1: TRichEdit;
Memo1: TMemo;
Edit1: TEdit;
Button1: TButton;
procedure Button1Click(Sender: TObject);
procedure FormActivate(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;

var
Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);
var
i, j, dl_str: integer;
stroka: string;

begin
Memo1.Clear;
if (Edit1.Text = '') or (RichEdit1.Text = '') then // Проверяем ввод исходных данных
begin
ShowMessage('Vvedite text');
exit;
end;

dl_str:= Length(Edit1.Text); // определяем длину строки поиска

i:= 1;

while i <= Length(RichEdit1.Text) - dl_str + 1 do // делаем перебор с учетом длины строки
begin
stroka:= '';
for j:= 0 to dl_str-1 do
stroka:= stroka + RichEdit1.Text[i+j]; // формируем строку для сравнения

if stroka = Edit1.Text then // если сравнилось
begin
RichEdit1.SelStart:= i-1;
RichEdit1.SelLength:= dl_str;
RichEdit1.SelAttributes.Style:= [fsBold]; // выделям жирным
RichEdit1.SelStart:= i-1;
Memo1.Lines.Add('Stroka ' + IntToStr(RichEdit1.CaretPos.Y + 1) + ' pos ' + IntToStr(RichEdit1.CaretPos.X + 1)); // отображаем координаты в Memo1
i:= i + dl_str; // переход на символ после найденного слова
end
else
i:= i+1; // переход на следующий символ
end;

end;

procedure TForm1.FormActivate(Sender: TObject); // активация формы, обнуление вводимых полей
begin
RichEdit1.Text:= '';
Edit1.Text:= '';
Memo1.Clear;
Memo1.ScrollBars:= (ssVertical); // установка вертикальной полосы прокрутки в Memo1
end;

end.


Процедура поиска по алгоритму Рабина-Карпа

procedure TForm1.Button1Click(Sender: TObject);
var
T, S: string;
i,j : longint;
n,m : longint;
v,w : longint;
k : longint;

const P : longint = 7919; {1000-е простое число}
D : longint = 256; {количество разных символов (количество всех возможных значений символьного типа char)}

begin
Memo1.Clear;
if (Edit1.Text = '') or (RichEdit1.Text = '') then
begin
ShowMessage('Vvedite text');
exit;
end;
RichEdit1.SelectAll;
RichEdit1.SelAttributes.Style:= [];

T:= RichEdit1.Text;
S:= Edit1.Text;
m:= Length(S);
n:= length(T);
v:=0;
w:=0;
for i:=1 to m do {вычисление v и w}
begin
v:=(v*D+ord(S[i])) mod P; {ord преобразует символ в число}
w:=(w*D+ord(T[i])) mod P;
end;

k:=1;
for i:=1 to m-1 do
k:=k*D mod P;
for i:=m+1 to n+1 do
begin
if w=v then {если числа равны, то строки принадлежат одному классу, и надо проверить совпадают ли они}
begin
j:=0;
while (j<m) and (S[j+1]=T[i-m+j]) do
j:=j+1;
if j=m then {окончательная проверка}

RichEdit1.SelStart:= i-m-1;
RichEdit1.SelLength:= m;
RichEdit1.SelAttributes.Style:= [fsBold];
RichEdit1.SelStart:= i-m-1;
Memo1.Lines.Add('Stroka ' + IntToStr(RichEdit1.CaretPos.Y + 1) + ' pos ' + IntToStr(RichEdit1.CaretPos.X + 1));
end;

if i<=n then
w:=(d*(w+P-(ord(T[i-m])*k mod P))+ord(T[i])) mod P;
end;

end;
Неизвестный
07.10.2010, 12:54
общий
Шичко Игорь:
Вероятно автору требовалось реализовать алгоритм Рабина-Карпа.
Неизвестный
07.10.2010, 13:24
общий
coremaster1:
Вполне возможно. Спасибо за уточнение. Сразу внимания не обратил. Уточню у автора вопроса.
Неизвестный
07.10.2010, 13:27
общий
Kreaman:
Написать программу поиска Рабина.

Принципиально ли использование в программе поиска использование этого метода (Рабина-Карпа)?
Если есть необходимость можно отредактировать модуль.
Неизвестный
07.10.2010, 13:44
общий
Здравствуйте. Да, по условиям задачи требовалось реализовать алгоритм поиска Рабина.
Неизвестный
07.10.2010, 14:01
общий
Kreaman:
В течение некоторого времени откорректирую код.
Неизвестный
07.10.2010, 14:39
общий
Kreaman:
Добавил в приложение процедуру поиска по алгоритму Рабина-Карпа.
Описание давать не буду оно уже есть:
Алгоритм Рабина-Карпа
Форма ответа