5 / 5 / 0
Регистрация: 20.06.2016
Сообщений: 87
|
||||||
1 | ||||||
Выведите количество подстрок строки a, являющихся циклическими сдвигами строки b25.03.2017, 20:26. Показов 4891. Ответов 8
Метки нет (Все метки)
Строки
(Время: 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 выведите целое число – ответ на задачу.
0
|
25.03.2017, 20:26 | |
Ответы с готовыми решениями:
8
Найти количество символов строки, не являющихся буквами Даны две строки: S1 и S2. Удалить из строки S1 последнюю подстроку, совпадающую с S2. Если таких подстрок нет, то вывести S1 без изменений Запись подстрок строки в массив Строки. Даны строки S и So. Найти количество вхождений строки So в строку S |
2386 / 1298 / 1492
Регистрация: 29.08.2014
Сообщений: 4,661
|
||||||
26.03.2017, 08:20 | 2 | |||||
тут форум технических специалистом, а не экстрасенсов. Где тест?
Добавлено через 2 часа 23 минуты если так сколько тестов проходит?
0
|
Модератор
|
||||||
26.03.2017, 08:43 | 3 | |||||
Если правильно путаю, ваш код можно переписать сильно короче:
Добавлено через 6 минут Про возможность нескольких одинаковых подстрок написали выше. Повторы тоже можно считать по-разному, выше считается, что 'аа' в 'ааааа' содержится 2 раза, но возможен вариант, когда 4. Тогда в строке 11 будет j:=PosEx(b,a,j+1)
0
|
2386 / 1298 / 1492
Регистрация: 29.08.2014
Сообщений: 4,661
|
||||||
26.03.2017, 09:36 | 4 | |||||
задача с acmp № 50
прошло все тесты,
Добавлено через 7 минут у вас считает только первое вхождение, а надо все. abcabc abc 1:cab 2:bca 3:abc -- а этих вхождений 2 3
0
|
2386 / 1298 / 1492
Регистрация: 29.08.2014
Сообщений: 4,661
|
|
26.03.2017, 09:48 | 6 |
bormant, прошу прощения
0
|
Модератор
|
||||||
26.03.2017, 10:08 | 7 | |||||
Joy,
не за что И все же, вопрос про j:=PosEx(b,a,1+j) vs. j:=PosEx(b,a,Length(b)+j) остался открытым или второй вариант не прошел тесты? Если проходят оба, то в тестовом наборе просто нет варианта проверки на этот счет. На мой вкус, SetLength можно безболезненно вынести за цикл, 1000 указателей -- это пустяки по сравнению в 1000 обращений к менеджеру кучи:
0
|
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
|
Модератор
|
|
26.03.2017, 14:44 | 9 |
Joy,
спасибо (на acmp я не пошел).
0
|
26.03.2017, 14:44 | |
26.03.2017, 14:44 | |
Помогаю со студенческими работами здесь
9
Даны строки S и S0. Удалить из строки S первую подстроку, совпадающую с S0. Если совпадений подстрок нет, то вывести S без изменений. Вставьте в середину первой строки вторую и выведите на экран самое короткое слово из полученной строки Заполнить строки матрицы циклическими перестановками первой строки Определить количество символов строки, не являющихся цифрами Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |