А если нужно сравнить 2 текстовых файла и вывести номера строк, которые совпадают, можно использовать этот алгоритм? и если да, то как?

Уточни, пожалуйста: совпадающие строки в разных файлах могут иметь разные номера (например: строка 2 файла 1 и строка 5 файла 2 совпадают), или речь идет о совпадении строк на одной и той же позиции (типа строка 2 в файлах одинаковая)?

Нужно использовать алгоритм Diff. Поищи в интернете.

совпадающие строки в разны файлах могут иметь разные номера.

Гым .
Самое естественное в этой ситуации с моей точки зрения - отсортировать оба файла (сохранив информацию о первоначальных положениях строк) в лексикографическом порядке (скажем, по возрастанию), потом пройтись по ним параллельно и найти, что требуется. Работы полно, короче. С самого начала - неясно, как сортировать: в создавать копию файла или считывать в массив и там орудовать? Первый способ медленный, второй может потребовать много памяти. Что скажешь?

мда, все оказывается не так просто...
Насчет того, что может потребовать много памяти или будет медленнее работать, это не важно, лишь бы работала)
Да, и вправду, логично сначала отсортировать, а потом сравнивать, правда, не совсем уверена, что все хорошо получится, во всяком случае у меня))

а можно просто каждую строку первого файла поочередно сравнить со всеми строками второго?

Можно, конечно... Как говорила героиня одного фильма "Можно и зайца научить курить" (С). Представляешь, сколько лишних действий ты сделаешь, если будешь постоянно туда-сюда бегать по файлу?

Ты лучше скажи, у тебя файлы большие, или не очень?

да, я понимаю, но просто не знаю уже как сделать.
ну вообще подразумеваются не маленькие, а что от этого зависит?

Думаю что время выполнения и объем ресурсов.

ну тогда это не столь важно, главное получить результат

Да поймите же наконец, что ресурсы компьютера ограничены!!!

*оля*
Ну, напишешь ты программу, которая будет читать строки из файлов в массивы и работать с ними (либо сортировать оба массива, как предлагал Lapp, либо отсортировать один, и потом бинарным поиском искать в нем строки из второго - не суть важно). Это будет прекрасно работать на маленьких файлах, скажем, по 200 строк. А попытаешься обработать файл из 1000 строк таким образом - что будет? А ничего - вылет из программы с сообщением о нехватке памяти... Это тебе нужно?

Так что определяй, что значит "не маленькие". И озвучь, наконец, каким ты компилятором пользуешься. То, что может один компилятор - для другого может оказаться неприемлемым.

Работоспособность.

Нет, Client. В некоторый момент сумка может порваться, лодка затонуть, селезенка надорваться. нет смысла говорить о "выполнении", если на него требуются годы (или даже дни) либо память 100 Гиг..

ну вообще, в задаче подразумевалось сравнивать файлы до 1500 строк, но если это реализовать слишком сложно, то можно задачу упростить, скажем, ввести заранее ограничение, пусть будет работать только для небольших файлов.
программы нам разрешают писать только в PascalABC или PascalABC.net

1500 - это как раз вполне терпимо. Если компилятор 32-разрядный, то можно и в памяти сделать.

А вот это для меня лично, например, непреодолимое препятствие.. Из-за этого устанавливать эту лабуду я не буду ((. Я использую FPC. Про алгоритм можно продолжать разговоры, но все адаптации к ABC, если они потребуются - сама, пожалуйста. Устраивает?

Оля, я разделяю тему. В следующий раз, пожалуйста, создавай свою тему, а не пость в чужие.

ок, в следующий раз буду создавать свою тему)

конечно устраивает!)
главное, хотя бы определиться, как все-таки сравнивать. Нашла статью, в которой сравнивают 2 файла с помощью арифметического кодирования строк числами с плавающей запятой. Но там по-моему все еще сложнее... вроде как расписан алгоритм, но не совсем понятно.

А чем не нравится мой алгоритм?

Оля,
да если у тебя есть возможность использовать PascalABC.NET - там делать нечего... Берешь файл. Один... Построчно читаешь его в переменную типа String, и запоминаешь в List<String> ее хеш. Любой. Скажем, MD5 (с использованием System.Security.Cryptography он вычисляется в 3 строки). А потом открываешь второй файл, и опять же построчно читаешь, вычисляешь для прочитанной строки тот же хеш, и ищешь его в списке.

"Всего и делов то..." (С) "Осенний марафон"

не, не в том дело, что он не нравится, просто я не знаю как его реализовать

Добавлено через 10 мин.


что-то я не совсем поняла как это сделать(((

а алгоритм volvo? Что в нем неясного?

Для некоторого упрощения: можно просто читать каждую строку из первого файла искать ее во втором.

Скажем, MD5 (с использованием System.Security.Cryptography он вычисляется в 3 строки).
вот это не понятно мне

Ну смотри. Существует такой алгоритм хеширования - Wiki- > MD5

Так вот, подобный хеш можно получить из любой строки, используя доступные из PascalABC.NET ДотНет-овские классы, а не писать функции для его вычисления самостоятельно:

uses 
  System.Collections.Generic, System.Security.Cryptography;

var
  prov:System.Security.Cryptography.MD5CryptoServiceProvider; 
  // это надо будет еще проинициализировать в основной программе
  
function CalcHash(s: string):string;
var
  a: array of byte;
  sb: System.Text.StringBuilder;
begin
  a := System.Text.Encoding.UTF8.GetBytes(s);
  a := prov.ComputeHash(a);
  sb := new System.Text.StringBuilder;
  foreach b: byte in a do sb.Append(b.ToString('x2').ToLower());

  CalcHash:= sb.ToString;
end;

В результате функция вернет хеш переданной в нее строки, который будет уникальным. Совпадение хешей будет означать совпадение строк, для которых они вычислялись.

Но это - уже реализация. Что в алгоритме-то непонятно?

теперь все понятно, спасибо! во всяком случае пока, сейчас попробую написать полностью программу, тогда думаю возникнут еще вопросы по мере написания)

выдает такую ошибку: Ошибка времени выполнения: В экземпляре объекта не задана ссылка на объект.
в строке
a := prov.ComputeHash(a);
я наверное что-то не дописала...что бы это могло быть?

А я предупреждал:


В самом начале основной программы надо инициализировать этот объект:

prov := new System.Security.Cryptography.MD5CryptoServiceProvider;

, только после этого его можно использовать. Обрати внимание, точно так же перед использованием внутри функции инициализируется System.Text.StringBuilder. Любой обзект перед тем, как к нему обращаться, нужно создать...

точно, написано же было, забыла. спасибо, теперь все нормально пока)

2 volvo:
я все же не понимаю, в чем тут пойнт применения хэшей. Почему нельзя сравнивать сами строки? В задаче нет ничего про секьюрити или там сжатие.. Сравнение строк может быть эффективнее использования хэшей в конечном итоге. Большинство строк начинаются с неравных символов - они сразу отметаются в самом начале. А для вычисления хэша всегда нужно прочитать всю строку. Зачем?

Только ради экономии памяти. Прочитать все строки файла в память (а строка может быть длинной), или хранить только хеш (фиксированной, причем небольшой) длины - это две большие разницы. И разницы эти тем больше, чем больше размеры файлов, с которыми нужно работать и чем длиннее в них строки.

В принципе, можно обойтись и без хеширования, конечно; надо будет прогнать пару тестов на больших файлах, посмотреть, насколько быстро MD5 вообще вычисляется, и насколько программа начинает подтормаживать, когда ей проходится работать со строками, а не их хешами... Если торможения не будет (или будет незначительное) - то работать с полными строками.

да, про память я как-то уже забыл тут.. Прикинул, что 1500 строк (по максимум 255 символов) берут не больше трети мега - и забыл..

Да, конечно, если нужно сжимать - то хэш. Но, судя по началу темы ("лишь бы работало")) - скорее всего не нужно.. Сравнить скорость двух подходов: с хэшированием и непосредственным чтением из файла - это действительно интересно. Результат, впрочем, будет сильно зависеть от системного дискового кэша..

идея сравнить 2 метода очень интересная )))

можно спросить, каким образом сохранить в List<String>? (

У него есть метод Add:

var
  L: System.Collections.Generic.List<string>;

... 
  // Инициализируем список:
  L := new System.Collections.Generic.List<string>;

  // Каким-то образом получаем строку, которую надо сохранить (назовем ее st)

  L.Add(st); // и заносим строку в список

За дополнительной информацией о .NET-овских контейнерах - сюда: MSDN -> System.Collections.Generic Namespace

а потом,для поиска тоже свой метод есть?

Естественно. Есть метод Find, есть FindAll (для поиска всех совпадений по заданному критерию), есть метод Contains, позволяющий определить просто есть ли в списке заданный элемент, есть IndexOf (чтобы определить индекс элемента, совпадающего с искомой строкой)... Методов - валом...

Мне кажется, или тема уже вышла далеко за рамки раздела "Задачи"? Теперь здесь в основном обсуждаются .NET-овские фишки. Может перенести в "Другие языки"? (я понимаю, что язык тот же, но... Туда и шарписты заходят, может помогут чем).

спасибо, все, с .NET-овскими фишками вопросов больше нет)
теперь другое... мы считаем хеш сразу для всей строки, а как посчитатеь его не сразу для всей, а для каждого слова в строке отдельно?

что не так в программе?

 var
rand8: array[0..255] of integer;
st: string;
line: string;
F: text;
f_name: string;

procedure init;
var
i: integer;
begin
randomize;
for i:=0 to 255 do
rand8[i]:=random(255);
end;

function h(st: string): integer;
Var
Sum: longint;
I: integer;
Begin
For i:=0 to length(st) do
Sum := sum + ord(st[i]) xor rand8[i];
H:=sum mod 256;
end;

begin
writeln('введите имя файла');
readln(f_name);
assign(f,f_name);
reset(f);
while not eof(f) do begin
readln(line);
st:=line;
init;
h(st);
writeln (h(st));
end;
close(f);
end. 

.

все, нашла ошибку, сорри