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

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

Вернуться   Форум программистов > Delphi программирование > Паскаль, Turbo Pascal, PascalABC.NET
Регистрация

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

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

Ответ
 
Опции темы Поиск в этой теме
Старый 05.02.2014, 22:03   #1
8Observer8
Старожил
 
Аватар для 8Observer8
 
Регистрация: 02.01.2011
Сообщений: 3,322
По умолчанию Задачка о поиске подстроки

Привет!

У меня вопрос по этой задачке: http://acmp.ru/index.asp?main=task&id_task=50

В обсуждении (http://acmp.ru/asp/gb.asp?id=50) написано, что:

Цитата:
abababab abab ответ: 5
Не могу понять почему.

Первый сдвиг (циклический сдвиг влево): baba
Во входной строке 1 совпадение

Второй сдвиг: abab
Во входной строке 2 совпадения

Третий сдвиг: baba
Во входной строке 1 совпадение

Четвёртый сдвиг: abab
Во входной строке 2 совпадение

Получается, что ответ: 6

Похоже я не понял задачу. Поясните, пожалуйста, в чём я заблуждаюсь.

Заранее спасибо за ответ!
8Observer8 вне форума Ответить с цитированием
Старый 05.02.2014, 22:16   #2
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

abababab abab
1) abababab
2) abababab
3) abababab
4) abababab
5) abababab

Последний раз редактировалось Poma][a; 05.02.2014 в 22:29.
Poma][a вне форума Ответить с цитированием
Старый 05.02.2014, 22:33   #3
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

abababab abab ответ: 5
Речь о циклических сдвигах, тогда исходная abab не считается (не сдвиг) и 4 получается. Понял так. Если считается то 6

PS

abababab abab

если рассматривать только abab и baba (не повторы циклических сдвигов) и попадание с перекрытием, то первая входит 3, вторая 2
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию

Последний раз редактировалось Аватар; 05.02.2014 в 22:43.
Аватар вне форума Ответить с цитированием
Старый 06.02.2014, 07:20   #4
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

Вот.. Сдал..
Код:
var
    a : array [1..100] of string;
    k : Integer;
 
function Next(s : string) : string;
begin
    Next := Copy(s, 2, Length(s))+s[1]
end;
 
function AlreadyExist(s : string) : Boolean;
var
    i : Integer;
 
begin
    for i := 1 to k do
        if a[i] = s then begin
            AlreadyExist := TRUE; Exit
        end;
 
    Inc(k);
    a[k] := s;
    AlreadyExist := FALSE
end;
 
function Count(s, substr : string) : Integer;
var
    t : Integer;
begin
    t := Pos(substr, s);
    if t > 0 then
        Count := 1 + Count(Copy(s, t+1, Length(s)), substr)
    else
        Count := 0;
end;
 
var
    sm, sub : string;
 
    cnt, i, n : Integer;
begin
        Reset(input, 'input.txt');
        Assign(output, 'output.txt');
    ReadLn(sm);
    ReadLn(sub);
    n := Length(sub);
 
    cnt := 0;
 
 
    for i := 1 to Length(sub) do begin
        if AlreadyExist(sub) then begin
                sub := Next(sub);
                Continue
        end;
        cnt := cnt+Count(sm, sub);
        sub := Next(sub)
    end;
    WriteLn(cnt)
end.

Последний раз редактировалось Poma][a; 06.02.2014 в 07:43.
Poma][a вне форума Ответить с цитированием
Старый 06.02.2014, 10:01   #5
8Observer8
Старожил
 
Аватар для 8Observer8
 
Регистрация: 02.01.2011
Сообщений: 3,322
По умолчанию

Цитата:
Сообщение от Аватар Посмотреть сообщение
abababab abab ответ: 5
Речь о циклических сдвигах, тогда исходная abab не считается (не сдвиг) и 4 получается.
Исходный считается, так как это последний пятый сдвиг. Поэтому исходную строку abab можно сразу искать.


Poma][a, огромное спасибо! Вечером разберу.

Правильно я понимаю?
abcabc
abc
1) bca abcabc
2) cab abcabc
3) abc abc|abc
Ответ: 4

Тогда вот здесь:
1) abababab
должно два раза считаться (как и в варианте №3 выше):
1) abab|abab
8Observer8 вне форума Ответить с цитированием
Старый 06.02.2014, 10:05   #6
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

Цитата:
должно два раза считаться (как и в варианте №3 выше):
Скорее 3
abababab
abababab
abababab
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Старый 06.02.2014, 10:14   #7
8Observer8
Старожил
 
Аватар для 8Observer8
 
Регистрация: 02.01.2011
Сообщений: 3,322
По умолчанию

Цитата:
Сообщение от Аватар Посмотреть сообщение
Скорее 3
abababab
abababab
abababab
Да, точно. Спасибо большое! Вы меня натолкнули на мысль, что подстроку нужно искать только один раз для каждого сдвига.

А как тогда быть с этим?
abcabc
abc
1) bca abcabc
2) cab abcabc
3) abc abc|abc
Ответ: 4
8Observer8 вне форума Ответить с цитированием
Старый 06.02.2014, 10:52   #8
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

И чем 4 не устраивает? 1+1+2
1) bca abcabc
2) cab abcabc
3) abc abcabc
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Старый 06.02.2014, 11:00   #9
8Observer8
Старожил
 
Аватар для 8Observer8
 
Регистрация: 02.01.2011
Сообщений: 3,322
По умолчанию

Цитата:
Сообщение от Аватар Посмотреть сообщение
И чем 4 не устраивает? 1+1+2
1) bca abcabc
2) cab abcabc
3) abc abcabc
Устраивает. Кажется я начинаю понимать. В главной строке нужно искать все разные подстроки (на разных позициях) для одного сдвига. А одинаковые сдвиги не нужно искать. Поэтому в следующем примере ответ: 5

Цитата:
Сообщение от Poma][a Посмотреть сообщение
abababab abab
1) abababab
2) abababab
3) abababab
4) abababab
5) abababab
Хотя строка abab имеет четыре сдвига, но нам нужно искать только два, так как остальные два - повторяются.

Последний раз редактировалось 8Observer8; 06.02.2014 в 11:03.
8Observer8 вне форума Ответить с цитированием
Старый 06.02.2014, 12:45   #10
8Observer8
Старожил
 
Аватар для 8Observer8
 
Регистрация: 02.01.2011
Сообщений: 3,322
По умолчанию

Цитата:
Сообщение от Аватар Посмотреть сообщение
И чем 4 не устраивает? 1+1+2
1) bca abcabc
2) cab abcabc
3) abc abcabc
Да, всё верно. Но нагляднее так написать:
abcabc
abc
1) bca abcabc
2) cab abcabc
3) abc abcabc
4) abc abcabc
8Observer8 вне форума Ответить с цитированием
Ответ


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

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
В поиске программы tRUSty Софт 6 29.08.2011 17:45
Глюк в поиске? garik64 Microsoft Office Word 2 20.01.2011 13:54
Ошибка в поиске... twister_answer Помощь студентам 0 08.01.2011 12:06
Ошибка в поиске. ПлоМбиРка Помощь студентам 0 01.06.2010 17:13
такая задачка..в принцепе не сложная даже новичку но в поиске ее не реально найти из за условия NEMO1991 Паскаль, Turbo Pascal, PascalABC.NET 11 06.06.2009 01:03