Форум программистов, компьютерный форум, киберфорум
Наши страницы
Free Pascal
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/6: Рейтинг темы: голосов - 6, средняя оценка - 4.67
max_besheniy
25 / 25 / 4
Регистрация: 21.11.2013
Сообщений: 208
1

Найти наибольшую общую подстроку двух строк

28.12.2013, 14:34. Просмотров 1137. Ответов 3
Метки нет (Все метки)

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

Лексикографический порядок — упорядоченный по алфавиту. Своё название лексикографический порядок получил по аналогии с сортировкой по алфавиту в словаре.

естественный порядок на неотрицательных целых числах в любой позиционной системе счисления, записанных в разрядной сетке фиксированной длины (000, 001, 002, 003, 004, 005, …, 998, 999)
порядок слов в словаре. Предполагается, что буквы можно сравнивать, сравнивая их номера в алфавите. Тогда лексикографический порядок — это, например, А < АА < ААА < ААБ < ААВ < АБ < Б < … < ЯЯЯ.
Входные данные:
Во входном потоке даны две строки, каждая длиной не более 250 символов, состоящие из заглавных английских букв.

Выходные данные:
В выходной поток вывести единственную строку символов.

Пример входного файла (input.txt):
JHQDULKHUAGKEPDMTL
FGGKMJLRDULKHUAGTMINCPVX
Пример выходного файла (output.txt):
DULKHUAG

Задавал ее уже на форуме но не прошли все тесты. Был предложен следующий код
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
var s1,s2,s:string;
    i,j,mx,max:byte;
begin
readln(s1);
readln(s2);
if length(s1)>length(s2) then max:=length(s1)
else
max:=length(s2);
for i:=length(s1)+1 to max do
s1:=s1+' ';
for i:=length(s2)+1 to max do
s2:=s2+' ';
mx:=0;
for i:=1 to max do
for j:=i to max do
if (pos(copy(s1,i,j-i+1),s2)>0)and(j-i+1>mx) then
 begin
  mx:=j-i+1;
  s:=copy(s1,i,j-i+1);
 end;
 
write(s);
end.
30 процентов тестов не работают возможно из-за Если таких подстрок несколько, то вывести ту, которая в лексикографическом порядке меньшая. . Помогите пожалуйста
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.12.2013, 14:34
Ответы с готовыми решениями:

Даны две строки. Найти наибольшую общую подстроку двух строк
Даны две строки. Найти наибольшую общую подстроку двух строк. Если таких...

Найти самую длинную общую часть двух строк
заданы две строки.Найти самую длинную их,общую часть.

Динамические структуры. Найти количество строк, содержащих данную подстроку
дана последовательность строк. найти количество строк, содержащих данную...

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

Построить общую касательную для двух окружностей
Построить общую касательную для окружностей с центром (x1,y1), радиусом R1 и...

3
al1as
385 / 73 / 31
Регистрация: 13.04.2012
Сообщений: 127
29.12.2013, 01:06 2
Попробуйте этот бред сумасшедшего:
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
var
  s1,s2,s,tmp : string;
  i,k,N,m,l : integer;
  Strs : array of string; //содержит все общие подстроки
 
begin
  Writeln('Введите строки');
  Readln(S1);
  Readln(S2);
  m := 0;
  k := 1;
  if Length(S1) > Length(S2) then
  begin
    tmp := s2;
    s2 := s1;
    s1 := tmp;
  end;
  N := Length(s1);
  SetLength(Strs,Trunc((n+1)*n/2)+1); // Макс. число таких подстрок - сумма ар. прогр.(если стр. совпадают)
  for i := 1 to N do  // Формируем массив ВСЕХ общих подстрок
  begin
    k := 1;
    while k <= N-i+1 do
    begin
      if Pos(Copy(s1,k,i),s2) > 0 then
      begin
        Strs[m] := Copy(s1,k,i);
        inc(m);
      end;
      k := k + 1;
    end;
  end;
  m := m - 1;
  s := Strs[m];
  l := Length(Strs[m]);
  for i := 1 to m do  // Ищем наибольший по длине и наименьший по лекс. порядку среди наибольших по длине
    if (Length(Strs[i]) = l) and (Strs[i] < s)  then
      s := Strs[i];
  for i := 0 to m do // Оставил для проверки
    Writeln(Strs[i]);
  Writeln('Результат - ',s);
  Readln;
end.
1
Cyborg Drone
Модератор
5296 / 3174 / 2442
Регистрация: 17.08.2012
Сообщений: 10,188
29.12.2013, 01:21 3
max_besheniy, добавить лексикографическую проверку в найденную Вами программу, и всё:
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
{...}
var s1,s2,s,p:string;
{...}
if (pos(copy(s1,i,j-i+1),s2)>0)and(j-i+1>=mx) then
 begin
  mx:=j-i+1;
  p:=copy(s1,i,j-i+1);
  if (mx>length(s))
   then s:=p
   else if p<s then s:=p
 end;
{...}
0
max_besheniy
25 / 25 / 4
Регистрация: 21.11.2013
Сообщений: 208
29.12.2013, 01:26  [ТС] 4
А ваш бред сумасшедшего работает)
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.12.2013, 01:26

Найти скалярное произведение двух строк матрицы
На внешнем носителе (в файле) построчно подготовлены элементы матрицы А(m,n)....

Найти сумму элементов двух первых строк матрицы
4) Составить программу, которая в данной действительной квадратной матрицы...

Найти количество строк матрицы, в которых более двух нулей
ПОМОГИТЕ ПОЖАЛУЙСТА Найти количество строк матрицы , в которых более двух...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru