поиск символьных последовательностей Опции

[c-chopper]

:low:
Найти наиболее длинную последовательность символов, которая встречается в данном текстовом файле (без переводов строк, размер не более 10 килобайт) более одного раза.

единственное, что приходит в голову(пока, по крайней мере) это тупой перебор комбинаций символов. но это неправильно.
прошу помощи :molitva:

[Altair]

Предлагаю такой способ.
Сначала выделяем вообще все подпоследовательности символов (последовательностть символов это более или 2 идущих подряд одинаковых симв), а затем имею все подпоследовательнотсти ищем ту, что нужно.

а вот тебе пример как разбить на подпоследовательности:
(процедура выделяет подпоследовательности)

 var s:string;
procedure getposl(s:string);
var i:byte; ss:string; b:boolean;
begin
 ss:=''; b:=false;
 for i:=1 to length(s) do
 begin
  if b then begin ss:=ss+s[i] end; {next}
  if (s[i]=s[i+1]) and (b=false) then begin ss:=ss+s[i]; b:=true; end; {new}
  if ((NOT((s[i]=s[i+1])))or (i=length(s))) and (b=true) then begin
   if ss<>'' then {*****}writeln(ss);{*****} ss:='';b:=false end;
 end
end;

begin
 readln(s);
 getposl(s)
end.

то есть что бы сохранить последовательности надо вместо
{*****}writeln(ss);{*****} описать процедуру сохранения где-то (все равно где - список, массив) слова ss...

[Atos]

Надо уточнить : имеется в виду последовательность одинаковых символов или последовательность любых символов? В первом случае работает вариант, который дал Oleg_Z, а во втором ... тут всё гораздо интереснее... надо подумать B)

[c-chopper]

имеется в виду последовательность одинаковых символов или последовательность любых символов?

любых, к сожалению

как вам такой вариант: сохраняем текст в массив типа char. берём его первый элемент(первую букву текста) и идём по массиву до первого совпадения. далее проверяем совпадают ли символы, следующие за найденными. если да, то запоминаем где-нить полученную последовательность. далее проверяем следующую букву, если совпадает- добавляем её к последовательности, если нет- продолжаем поиск дальше по массиву.
большой минус- придётся пробегать по массиву хз сколько раз.... а массив не маленький- 10кб

[volvo]

А как это отработает на таком массиве, например:
"abacbcbcbcddabacbcbcbcde"
Выдаст подпоследовательность "ab"? Но ведь есть еще "abacbcbcbcd" !!!

[c-chopper]

найдёт ab, проверит какая буква следует за b обоих случаях, обнаружит совпадение, добавит найденную букву в получаемую строку и продолжит так дальше до несовпадения. в итоге и должно получиться "abacbcbcbcd"

Сообщение отредактировано: c-chopper - 12.05.2005 20:55

[volvo]

Кстати, посмотри что я нашел: http://www.hardline.ru/1/11/1352/1750-5.html... Почитай, может натолкнет на идею?

[Atos]

Кстати, посмотри что я нашел:

Хорошая статья!

Да, и ещё момент тут надо уточнить: последоватьльности могут пересекаться?
То есть, считаем мы, что в строке abababa две последовтельности ababa , или нет?

[c-chopper]

Atos
необходимо найти самую длинную. в данном случае очевидно только abababa

volvo, спасибо. но 10кб текста это около 10000 символов. а BP такие здоровые массивы(10000х10000) не понимает , а с деревьями я вообще ничего не понял

[volvo]

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

[Atos]

Atos
необходимо найти самую длинную. в данном случае очевидно только abababa

Так ведь в твоём задании "Найти наиболее длинную последовательность символов, которая встречается <... > более одного раза"
Сама abababa, очевидно, только один раз.

[c-chopper]

угу... я почему-то решил, что abababa часть строки %)

[c-chopper]

:fire:

program individualnoe_n14;
uses crt;
type ar=array[1..10000] of ^char;
     mass=^ar;
var
   f:text;
   name,found:string;
   tekst:^mass;

{----------PROCEDURES-------------}
procedure GENER_FILE(var f:text);
{лень- двигатель процесса: генерим файл и вставляем в него что нужно найти}
var i:integer; c:byte;
begin
randomize;
rewrite(f);
for i:=1 to 24000 do begin
c:=random(123);
case c of
65..90: write(f,chr©);
97..122: write(f,chr©);
0..64,91..96: i:=i-1 end;
end;
close(f); writeln('File ',name,' is ready. Press any key'); readkey end;


procedure TEXT2MASS(var tekst:mass); 
{для удобства работы перекидываем файл в массив.}
{ во избежание проблем с количеством памяти отправляем всё куда-нить подальше из 64 кб}
var w:char; i,j:integer;
begin new(tekst);
for i:=1 to 11000 do begin new(tekst^[i]); tekst^[i]^:='~' end;
i:=1;
reset(f);
while not eof(f) do begin
read(f,w); tekst^[i]^:=w; i:=i+1; {write(w); }end;
writeln('array is ready');
end;


procedure OCENKA(var found:string; tekst:mass);    {понеслась.....}
var i,j,u,k:integer; srav:string;             
begin
j:=1; i:=2; srav:=''; found:=''; 

while tekst^[j]^<>'~' do begin
if tekst^[j]^=tekst^[i]^ then begin
                              srav:=''; k:=j; u:=i; i:=i+1;
                              while tekst^[k]^=tekst^[u]^ do begin
                                                             srav:=srav+tekst^[k]^;
                                                             k:=k+1; u:=u+1
                                                             end;
                              end
                         else i:=i+1;
if length(srav)>length(found) then found:=srav;
if tekst^[i]^='~' then begin j:=j+1; i:=j+1 end;
                         end;
end;

{================PROGRAM BODY=============}
BEGIN
clrscr;
{writeln('Type a filename'); readln(name); assign(f,name); } assign(f,'c:\bigfile.txt');
{gener_file(f);  }
text2mass(tekst^);
ocenka(found,tekst^);
writeln;
writeln('found=',found,'; consists of ',length(found),' chars'); readkey;
END.

ета фигня работает в TMT Pascal Lite в районе 1 секунды, а в долбанном BP от 5 до 10 с хвостом. проверять препод будет в борланде. после чего повесит мя на мышином кабеле.
SOS
если не хотите писать прогу, то хоть популярно растолкуйте алгоритм из приведённой выше ссылки. а то для первого курса сложновато как-то... мы по строкам галопом пробежали... и всяких подстрок с суффиксами и расширениями строки не проходили.... я как только начинаю читать тут же "повисаю" от кол-ва незнакомых терминов...

[Atos]

На первый беглый взгляд:
1) Можно открыть файл как нетипизированный с длиной записи 1, и вместо read использовать BlockRead, копируя в массив не по одному символу, а сразу весь файл. Получится чуть быстрее, правда, скорее всего, ненамного. Но и на доли секунды оптимизировать не помешает.
2)

Код

^char

Зачем??? У тебя и без этого массив динамический. Используя вместо char указатель на char, ты теряешь и время на выделение памяти под каждый символ, и время на переход по адресу в куче при каждом обращении к нему, и до 40 килобайт места в куче (каждый указатель весит 4 байта)
3) Чего -то с самим алгоритмом не того... Надо разобраться, он вообще правильно работает? Счас скачаю, попробую у себя посмотреть.

Мне самому эта задача интересна, скачал статью по той ссылке, чтобы дома на досуге разобраться, но чего-то не то с кодировкой оказалось c-chopper, тебе к какому дню надо сдать? Попробую сочинить чего-нито.

З.Ы. Кстати, всё-таки сомнительно, чтобы от первокурсников требовалось применять деревья в задании. Наверное, уложиться в 1 секунду можно постараться как-нибудь по-другому...

[c-chopper]

Чего -то с самим алгоритмом не того... Надо разобраться, он вообще правильно работает?

вроде да.... генерил файл, вставлял туда несколько повторяющихся слов разной длины- всё нашёл правильно(т.е. самое длинное)...

тебе к какому дню надо сдать?

6 июня последний срок(лучше раньше, есессно). а у меня ещё, как говорится, конь не валялся... ну или малость повалялся =) и ушёл

Кстати, всё-таки сомнительно, чтобы от первокурсников требовалось применять деревья в задании. Наверное, уложиться в 1 секунду можно постараться как-нибудь по-другому...

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

[c-chopper]

использовать можно всё, что считаешь нужным.

Сообщение отредактировано: c-chopper - 17.05.2005 19:30

[volvo]

если не хотите писать прогу, то хоть популярно растолкуйте алгоритм из приведённой выше ссылки.

Да пойми ты, что НЕ ДОЛЖЕН тебе никто ничего растолковывать. Иди в "Задачи на заказ", плати деньги, и потом будешь ТРЕБОВАТЬ.

[c-chopper]

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