Версия для печати темы
Нажмите сюда для просмотра этой темы в обычном формате
Форум «Всё о Паскале» _ Задачи _ Задача на строки
Автор: Лаврентий 1.03.2005 16:37
Пацаны, привет! Я уже пару дней обхожу весь Инет и в частности читаю все, что есть на этотм форуме, но проблему не могу решить. Не хотел вам беспоеоить, но пришлось. Итак, мне нужно сравнить две строки. Если во второй встречаются любые последовательности символом первой.
Нашел в Инете такую программу, но в не есть ошибка (я ее выделил !!! !!! )
Вот ее задача.
Задание 3.13. Вхождение строки с разрядкой
Строка S2 может входить в более длинную строку S1 в общепринятом смысле, когда непрерывная подпоследовательность символов строки S1совпадает с цепочкой символов S2. Однако возможна и другая ситуация, когда строка S2 входит в строку S1 с разрядкой. При этом символы S2 с равномерным шагом через 1, 2, 3 или более символов встречаются в строке S1.
Например, для строк S1="ABCBEEC" и S2="ABC" имеют место обычное (с нулевым шагом разрядки) вхождение (символы 1, 2 и 3 в строке si) и вхождение с разрядкой в 2 символа (символы 1, 4 и 7 в строке S1).
Составить программу, которая:
запрашивает и вводит анализируемые строки S1 и S2;
определяет, входит ли строка S2 в S1, выдает шаг разрядки и номера соответствующих позиций в строке si.
Задача программы — определить все возможные варианты вхождения S2 в S1.
Совет 1 (общий)
Идея поиска довольно проста. Обозначим через h шаг по индексу в строке S1, с которым выбираются символы, сравниваемые с символами S2. Для нулевой разрядки h=l, для выборки через символ h=2 и т. д. Очевидно, что начинать
сравнение надо с символа S1[I], совпадающего с первым символом S2. Однако реализация этой идеи может быть разной. Например, из строки si можно извлечь с заданной разрядкой нужное число символов и результат сравнить с S2. Более эффективно совместить эти две операции и сравнивать извлекаемый из S1 символ с очередным символом S2, прекращая выборку при первом несовпадении. Указанный подход был реализован победителем областной студенческой олимпиады В. Мартьяновым (апрель 2000 г.), на базе программы которого и построены приведенные ниже примеры. Наиболее оригинальной, на наш взгляд, является проверка условия (h=l) или (L2>1). Здесь L2—длина второй строки.
Программа 3_13.pas
(Поиск вхождения S2 в S1 с разрядкой}
uses crt;
var
s1,s2:string;
i,j,k,h,L1,L2:integer;
label 1;
begin
clrscr;
write('Введите S1: ');
readln (si);
Ll:=length(sl);
write('Введите S2: ');
readln (s2);
L2:=length(s2);
k:=0;
for h:=1 to L1 do
if (h=1)or(L2>1) then
for i:=1 to L1-(L2-1)*h do
if s1[i]=s2[l] then begin
for j:=2 to L2 do
if s1[i+(j-l)*h]os2[j] then goto 1; !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
write ('Шаг: ',h-l:2,' Позиции: ',i);
for k:=l to L2-1 do
write('-',i+k*h);
writeln;
k:=l;
1:
end;
if k=0 then writeln('Строка S2 не входит в S1');
readln;
end.
Код заключаем в теги !!!
Автор: volvo 1.03.2005 17:58
Улучшенная версия: (избавляемся от Goto)
uses crt;
var
s1, s2: string;
i,j,k,h,L1,L2: integer;
do_more: boolean;
begin
clrscr;
write('input S1: ');
readln(s1); { s1 := 'this is a t -e -s -t -'; }
L1:=length(s1);
write('input S2: ');
readln(s2); { s2 := 'test'; }
L2:=length(s2);
k:=0;
for h:=1 to L1 do
if (h=1)or(L2>1) then
for i:=1 to L1-(L2-1)*h do
if s1[i]=s2[1] then
begin
do_more := true;
for j:=2 to L2 do
if s1[i+(j-1)*h] <> s2[j] then
begin do_more := false; break end;
if do_more then
begin
write('step: ',h-1:2,' position: ',i);
for k:=1 to L2-1 do
write('-',i+k*h);
writeln;
k:=1;
end;
end;
if k=0 then writeln('string S2 not exists in S1');
readln;
end.
Тестировалось на закомментированных строках...
Добавлено (1.03.05 16:07):
Ну или вот так:
Прикрепленные файлы
STR.PAS ( 1006 байт )
Кол-во скачиваний: 260Автор: Лаврентий 2.03.2005 16:38
Огромное спасибо!
Я ее пропустил - все работает, сейчас буду разбираться в исправлениях.
Еще раз искреннее спасибо! Приятно...