Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 25.05.2011, 14:47   #1
WizzzIDizzzI
 
Регистрация: 21.05.2011
Сообщений: 4
По умолчанию Алгоритм Кнута — Морриса — Пратта. Ошибка!! Паскаль

Помогиет найти ошибку.
Задание:
1. Найти самое длинное совпадение символов(включая пробелы) из 1-го предложения со 2-м.
2. Подсчитать количество сравнений символов образа с текстом.
Алгоритмом Кнута — Морриса — Пратта
Код:
uses crt;

var
sSentence1,sSentence2,sWord,sFindWo rd:string;

iCountKnutMorrisPratt:integer;
bFoundWord:boolean;

i,j,k:integer;

function KnuthMorrisPratt( const sNeedle, sHayStack : string ) : Integer;
var
F: array[byte] of Integer;
k, i, m: integer;
begin
m := 0;
KnuthMorrisPratt := m;
F[1] := 0;
k := 0;
for i := 2 to Length(sNeedle) do
begin
while (k > 0) and (sNeedle[k+1] <> sNeedle[i]) do
k := F[k];
if sNeedle[k+1] = sNeedle[i]
then
Inc(k);
F[i] := k;
end;
k := 0;
for i := 1 to Length(sHayStack) do
begin
while (k > 0) and (sNeedle[k+1] <> sHayStack[i]) do
begin
inc(m);
KnuthMorrisPratt := m;
k := F[k];
end;
if sNeedle[k+1] = sHayStack[i]
Then
Inc(k);
if k = Length(sNeedle)
Then
begin
bFoundWord := true;
sFindWord := sNeedle;
Break;
end;
end;
end;

{////////////////////////////////////////////////////////}

begin
clrscr;

sSentence1 := 'sent sentence seniu';
sSentence2 := 'sents sent sentes sentenc';

iCountKnutMorrisPratt := 0;
bFoundWord := false;
i := length(sSentence1);
sFindWord := '';

repeat
begin
j := 1;
repeat
begin
sWord := '';
for k := 0 to i-1 do
begin
sWord := sWord + sSentence1[j+k];
end;
iCountKnutMorrisPratt := iCountKnutMorrisPratt + KnuthMorrisPratt(sSentence2, sWord);
j := j+1;
end;
until(bFoundWord or (j+i-1>length(sSentence1)));
i := i-1;
end;
until(bFoundWord or (i=0));

writeln('KnuthMorrisPratt');
writeln('Max word in sentences: "', sFindWord, '"');
writeln('Number of comparisons = ',iCountKnutMorrisPratt);
writeln('');

readln;
end.
WizzzIDizzzI вне форума Ответить с цитированием
Старый 25.05.2011, 16:46   #2
KobolD
Форумчанин
 
Регистрация: 10.06.2010
Сообщений: 239
По умолчанию

Смотри как я умею
Код:
writeln('KnuthMorrisPratt');
writeln('Max word in sentences: "', sFindWord, '"');
а ты так можешь?

P.S. добавляй коментарии в код, думаешь интересно гадать что ты хотел сделать конкретной процедурой или циклом.
Чтобы слова не расходились с делом, нужно молчать и ничего не делать.
KobolD вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Кто читал Дональда Кнута? vedro-compota Свободное общение 24 08.06.2010 13:43
Алгоритм Кнута-Морриса-Пратта или Рабина-Карпа (язык С++). Может у кого-нибудь есть готовый рабочий ? Беата Помощь студентам 7 27.03.2010 10:50
Алгоритм Кнута-Морриса-Пратта Crazy_Gamer Помощь студентам 1 17.12.2009 18:27