5 / 5 / 0
Регистрация: 20.06.2016
Сообщений: 87
1

Выведите количество подстрок строки a, являющихся циклическими сдвигами строки b

25.03.2017, 20:26. Показов 4891. Ответов 8
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Строки

(Время: 1 сек. Память: 16 Мб Сложность: 34%)
Циклическим сдвигом строки s называется строка sksk+1sk+2…s|s|s1s2…sk-1 для некоторого k, здесь |s| - длина строки s. Подстрокой строки s называется строка sisi+1…sj-1sj для некоторых i и j. Вам даны две строки a и b. Выведите количество подстрок строки a, являющихся циклическими сдвигами строки b.

Входные данные

Первая строка входного файла INPUT.TXT содержит строку a (1 ≤ |a| ≤ 1000). Во второй строке входного файла записана строка b (1 ≤ |b| ≤ min(100,|a|)). Обе строки состоят только из символов латинского алфавита и цифр.

Выходные данные

В выходной файл OUTPUT.TXT выведите целое число – ответ на задачу.
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
44
45
46
47
48
49
50
var
s,ss:string;
c,i,j,q,ans:longint;
bol:boolean;
begin
readln(s);
readln(ss);
i:=1;
 
for c:=1 to length(ss) do begin
ss:=ss[length(ss)]+copy(ss,1,length(ss)-1);
writeln(ss);
i:=1;
 
while i<=length(s) do begin
j:=1;
bol:=false;
    if s[i]=ss[j] then begin
        q:=i;
        bol:=true;
        while true  do begin
            inc(j);
            inc(q);
            if s[q]<>ss[j] then begin
            bol:=false;
            break;
            end;
            if (j=length(ss)) then begin
 
            break;
            end;
            if (q=length(s)) then begin
            if j<length(s) then bol:=false;
            break;
            end;
        end;
 
    end;
    if bol then begin
    i:=q+1 ;
 
    inc(ans);
    end
    else
    inc(i);
end;
 
end;
writeln(ans);
end.
мой код не проходит 5 тест может поможете ?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
25.03.2017, 20:26
Ответы с готовыми решениями:

Найти количество символов строки, не являющихся буквами
Строки в языке Pascal 3. Вводим с клавиатуры произвольные строки определить и вывести на экран...

Даны две строки: S1 и S2. Удалить из строки S1 последнюю подстроку, совпадающую с S2. Если таких подстрок нет, то вывести S1 без изменений
Вот условие: Даны две строки: S1 и S2. Удалить из строки S1 последнюю подстроку, совпадающую с S2....

Запись подстрок строки в массив
Пользователь вводит строку из букв и пробелов. Записать все слова из этой строки (разделены одним и...

Строки. Даны строки S и So. Найти количество вхождений строки So в строку S
Помогите пожалуйста, как сделать эту задачу без этих вот строчек... B:=TRUE; и без команды INC......

8
Эксперт Pascal/Delphi
2386 / 1298 / 1492
Регистрация: 29.08.2014
Сообщений: 4,661
26.03.2017, 08:20 2
Цитата Сообщение от ProHacker Посмотреть сообщение
мой код не проходит 5 тест может поможете ?
тут форум технических специалистом, а не экстрасенсов. Где тест?

Добавлено через 2 часа 23 минуты
если так сколько тестов проходит?
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
uses Strutils;
var
  a,b:string;
  i,j,c:longint;
begin
  readln(a);
  readln(b);
  for i:=1 to length(b) do begin
     b:=copy(b,2,length(b))+b[1];
     j:=PosEx(b,a,1);
     while j>0 do begin c:=c+1;j:=posEx(b,a,j+length(b));end;
   end;
   write(c);
end.
0
Модератор
Эксперт Pascal/DelphiЭксперт NIX
7794 / 4617 / 2830
Регистрация: 22.11.2013
Сообщений: 13,112
Записей в блоге: 1
26.03.2017, 08:43 3
Если правильно путаю, ваш код можно переписать сильно короче:
Pascal
1
2
3
4
5
6
7
8
9
10
11
var
  a, b: String;
  j, r: Integer;
begin
  ReadLn(a); ReadLn(b);
  for j:=1 to Length(b) do begin
    b:=b[Length(b)]+Copy(b,1,Length(b)-1);
    Inc(r,Ord(Pos(b,a)>0));
  end;
  WriteLn(r);
end.
Если не прошли по времени, то этот вариант быстрее.

Добавлено через 6 минут
Про возможность нескольких одинаковых подстрок написали выше.
Повторы тоже можно считать по-разному, выше считается, что 'аа' в 'ааааа' содержится 2 раза, но возможен вариант, когда 4. Тогда в строке 11 будет j:=PosEx(b,a,j+1)
0
Эксперт Pascal/Delphi
2386 / 1298 / 1492
Регистрация: 29.08.2014
Сообщений: 4,661
26.03.2017, 09:36 4
задача с acmp № 50
прошло все тесты,
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
uses Strutils;
var
  a,b:string;
  i,j,c,k,l:integer;
  t:array of string;
begin
  readln(a);
  readln(b);
  for i:=1 to length(b) do begin
     b:=copy(b,2,length(b))+b[1];
     l:=0;
     for j:=0 to k-1 do if t[j]=b then l:=1;
     if l=0 then begin
       k:=k+1;
       setlength(t,k);t[k-1]:=b;
       j:=PosEx(b,a,1);
       while j>0 do begin c:=c+1;j:=posEx(b,a,j+1);end;
     end;
   end;
   write(c);
end.
Цитата Сообщение от bormant Посмотреть сообщение
Повторы тоже можно считать по-разному, выше считается, что 'аа' в 'ааааа' содержится 2 раза, но возможен вариант, когда 4. Тогда в строке 11 будет j:=PosEx(b,a,j+1)
в предыдущем коде у меня косяк - нужно было считать количество вхождений только для уникальных строк, полученных циклическим сдвигом.

Добавлено через 7 минут
Цитата Сообщение от bormant Посмотреть сообщение
Если правильно путаю, ваш код можно переписать сильно короче:
у вас считает только первое вхождение, а надо все.
abcabc
abc
1:cab
2:bca
3:abc -- а этих вхождений 2
3
0
Модератор
Эксперт Pascal/DelphiЭксперт NIX
7794 / 4617 / 2830
Регистрация: 22.11.2013
Сообщений: 13,112
Записей в блоге: 1
26.03.2017, 09:47 5
Цитата Сообщение от Joy Посмотреть сообщение
у вас
не-не, это всего-лишь алгоритм ТС, приведенный к естественному виду, я тут не при чём
0
Эксперт Pascal/Delphi
2386 / 1298 / 1492
Регистрация: 29.08.2014
Сообщений: 4,661
26.03.2017, 09:48 6
bormant, прошу прощения
0
Модератор
Эксперт Pascal/DelphiЭксперт NIX
7794 / 4617 / 2830
Регистрация: 22.11.2013
Сообщений: 13,112
Записей в блоге: 1
26.03.2017, 10:08 7
Joy,
не за что
И все же, вопрос про j:=PosEx(b,a,1+j) vs. j:=PosEx(b,a,Length(b)+j) остался открытым или второй вариант не прошел тесты? Если проходят оба, то в тестовом наборе просто нет варианта проверки на этот счет.

На мой вкус, SetLength можно безболезненно вынести за цикл, 1000 указателей -- это пустяки по сравнению в 1000 обращений к менеджеру кучи:
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
{$H+}
uses StrUtils;
var
  a: String;
  b: String[100];
  i, j, c, k: Integer;
  t: array of String;
begin
  ReadLn(a); ReadLn(b);
  SetLength(t,Length(b));
  for i:=1 to Length(b) do begin
     b:=Copy(b,2,Length(b))+b[1];
     j:=k-1; while (j>=0) and (t[j]<>b) do Dec(j);
     if j<0 then begin
       t[k]:=b; Inc(k);
       j:=PosEx(b,a,1);
       while j>0 do begin
         Inc(c); j:=PosEx(b,a,1+j);
       end;
     end;
   end;
   WriteLn(c);
end.
0
Эксперт Pascal/Delphi
2386 / 1298 / 1492
Регистрация: 29.08.2014
Сообщений: 4,661
26.03.2017, 14:22 8
j:=PosEx(b,a,Length(b)+j) - не проходит все тесты. Там обсуждение есть:
Вы неправильно поняли задачу. Сдвиг первой строки не нужно делать, только второй, причем повторяющиеся стоки, получаемые из второй строки при сдвигах не считаются. Задачу можно понять однозначно, для этого целых 4 примера.

Добавлено через 2 минуты
И это:
Поясните, если можно, третий тест: циклический сдвиг аа равен аа и искать его вхождения второй раз не нужно, а 6 получается потому, что в ааааааа есть шесть пересекающихся вхождений аа? Или пересекающиеся вхождения не считаются, а ищется аа (3 раза), сдвигается в аа и ещё получается 3 раза? Надеюсь, вы поняли о чём я. Заранее спасибо. Ещё один вопрос. Из имеющихся здесь обсуждений понятно, что тип string при проверке не ограничен 255 символов, а какова его максимальная длина?
Я Вас понял, конечно. Все пересечения считаются, т.е. строка "аа" входит в "ааааааа" 6 раз. Но после того, как происходит сдвиг строки "аа" мы получаем ту же "аа" и не рассматриваем ее. Нужно рассматривать только разные строки, которые могут получаться из исходной путем сдвига. Хотя это можно понять однозначно: ведь ясно, что рассматривая две подстроки с непустым пересечением мы имеем дело по сути с разными подстроками (несмотря на то, что строки равны могут быть). Ведь у подстроки есть еще позиция ее вхождения в оригинальную строку, тем подстрока и отличается от простой строки. А меня Вы поняли?
0
Модератор
Эксперт Pascal/DelphiЭксперт NIX
7794 / 4617 / 2830
Регистрация: 22.11.2013
Сообщений: 13,112
Записей в блоге: 1
26.03.2017, 14:44 9
Joy,
спасибо (на acmp я не пошел).
0
26.03.2017, 14:44
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
26.03.2017, 14:44
Помогаю со студенческими работами здесь

Даны строки S и S0. Удалить из строки S первую подстроку, совпадающую с S0. Если совпадений подстрок нет, то вывести S без изменений.
Даны строки S и S0. Удалить из строки S первую подстроку, совпадающую с S0. Если совпадений...

Вставьте в середину первой строки вторую и выведите на экран самое короткое слово из полученной строки
Вставьте в середину первой строки вторую и выведите на экран самое короткое слово из полученной...

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

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


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru