Найти самую длинную строку, которая является подстрокой всех слов
Требуется написать программу, которая принимает несколько слов, и нам нужно найти то, которое чаще всего повторяется. Подскажите, есть ли какие-нибудь функции? А то понятия не имею как это написать Пример ввода: Sample Samplin SamplingsFun Saplingdsajisfasfijoi Пример вывода: Sampl
Отслеживать
892 6 6 серебряных знаков 21 21 бронзовый знак
задан 22 ноя 2020 в 14:00
3 3 3 бронзовых знака
Задача не поставлена нормально. Кроме того, нужно показать свои размышления и попытки
22 ноя 2020 в 14:11
Ваши-то идеи где?
22 ноя 2020 в 14:16
Учебные задания допустимы в качестве вопросов только при условии, что вы пытались решить их самостоятельно перед тем, как задать вопрос. Пожалуйста, отредактируйте вопрос и укажите, что именно вызвало у вас трудности при решении задачи. Например, приведите код, который вы написали, пытаясь решить задачу
22 ноя 2020 в 14:16
1 ответ 1
Сортировка: Сброс на вариант по умолчанию
Судя по вашему вопросу ваш преподаватель не ждет от вас использование каких-либо «готовых функций». Это классическая задача на алгоритмы. Она сводится к нахождению общей подстроки попарно между всеми имеющимися строками. Алгоритм примерно такой:
- Берете первые 2 слова (обозначим их длины x1 и x2) и строите матрицу (двумерный массив) размером x1+1 на x2+1
- Заполняете первый столбец матрицы нулями
- Заполняете первую строку матрицы нулями
- Заполняете клетки на пересечении разных букв нулями
- Заполняете клетки на пересечении одинаковых букв значением равным значению на пересечении двух предыдущих индексов плюс 1 (то есть если сейчас вы смотрите индексы 5 и 7 и в заголовках этих двух индексов одинаковые буквы, то вы берете значение из клетки 4 и 6 и прибавляете к нему 1 и результат записываете в клетку с индексом 5 и 7)
Все пункты с 2 по 5 само собой делаются за один раз в двух вложенных циклах. После чего ваша таблица для первой пары слов готова.
- Находите в полученной матрице самое большое число.
- . и двигаясь по диагонали от него ( каждый раз уменьшая оба индекса на единицу переписываете посимвольно любой из заголовков матрицы — это и есть повторяющиеся символы в этой паре строк)
В итоге после сравнения первых двух слов у вас есть общая строка для этой пары, третью строку можно уже сравнивать с полученной подстрокой и тем самым уточнить полученный результат и так далее. Но нужно учитывать, что подстрок может оказаться несколько и тогда лучше отслеживать все варианты — лишние в ходе проверок сами должны отсеяться.
P.S.: Задача на столько типовая, что по ней и ей подобным есть целый ворох статей в вики, главное правильно сформулировать вопрос!
Решаем кодом: найти самую длинную вложенную строку
Продолжаем разбирать задачи с сайта LeetCode. На этот раз — посложнее:
Есть строка s — нужно найти длину самой длинной подстроки, в которой каждый символ используется только один раз.
если s = «abcabcbb», то ответ будет 3, потому что строка без повторений — это «abc»;
если s = «bbbbb», то ответ будет 1, потому что самая длинная подстрока тут будет из одного символа;
если s = «pwwkew», то ответ будет 3, потому что тут две самые одинаково длинные подстроки — «wke» и «kew», в которых по 3 символа.
Такие алгоритмы иногда используются для выявления закономерностей и поиска общих элементов, поэтому их тоже могут спросить на собеседованиях.
Решение: использовать встроенные функции для работы со строками
Самое простое решение — собирать отдельную подстроку из символов и смотреть каждый раз, есть очередной символ в этой подстроке или нет. Если нет — добавляем его в конец и смотрим дальше. А если очередной символ там уже есть, то в подстроке оставляем только то, что идёт после этого символа, и добавляем туда текущий.
Например, если у нас в подстроке хранится «abcdf» и мы снова встречаем b, то делаем так:
- Получаем номер символа b в подстроке → он равен 1 (если интересно, почему не 2, — почитайте, почему счёт в программировании начинается с нуля, а не с единицы).
- Формируем новую строку, начиная с 1 символа и до конца → «cdf».
- Добавляем к ней в конец наш текущий символ b → «cdfb».
Так шаг за шагом мы проверим все вложенные строки и найдём самую длинную без повторов. Звучит сложно, но в коде всё выглядит гораздо проще. Почитайте комментарии, чтобы разобраться в каждом шаге:
# исходная строка s = 'abcabcdcc' # здесь будет наш ответ res = 0 # на старте у нас пустая подстрока sub = '' # перебираем все символы в исходной строке for char in s: # если символа нет в подстроке if char not in sub: # добавляем его туда sub += char # смотрим, максимальный ли это результат, и если да — запоминаем его res = max(res, len(sub)) # если символ в подстроке есть else: # получаем индекс текущего символа в подстроке cut = sub.index(char) # сокращаем нашу подстроку: оставляем только то, что идёт после символа-дубликата, и добавляем к строке текущий символ sub = sub[cut+1:] + char # выводим результат на экран print(res)Решение: проверить всю вложенную строку
Зайдём с другой стороны — напишем функцию, которая будет проверять, есть в указанной подстроке повторяющиеся символы или нет. Логика будет такая:
- Передаём в функцию начальный и конечный индекс, который определяет границы подстроки.
- Заводим массив, в который будем складывать проверенные символы и проверять на дубли.
- По очереди проверяем все символы в указанном диапазоне и смотрим, есть ли очередной символ в нашем массиве.
- Если есть — выводим False, что означает, что в подстроке есть повторяющиеся символы.
- Если символа нет — добавляем его в наш массив.
- Если мы проверили все символы и ни одного не было в том массиве — возвращаем True, то есть повторов нет.
Теперь запишем это на Python:
# исходная строка s = 'abcabcdcc' # функция, которая проверит, есть ли в подстроке повторяющиеся символы # на вход отправляем начальную и конечную позицию в строке для проверки def check(start, end): # создаём пустое множество chars = set() # делаем цикл от начального до конечного символа for i in range(start, end + 1): # получаем очередной символ из строки c = s[i] # если символа уже есть в множестве if c in chars: # возвращаем False — в строке есть повторяющиеся символы return False # добавляем символ в множество chars.add(c) # если дошли досюда — возвращаем True return TrueТеперь перейдём к основной части. Раз мы научились проверять, есть повторы в подстроке или нет, то нам остаётся только найти и проверить все вложенные строки. Сделаем это обычным перебором с вложенным циклом: будем проверять все подстроки, сначала начиная с первого символа, потом со второго и так далее. При этом мы будем каждый раз считать и запоминать максимальную длину подстроки без повторов, которая у нас получилась:
# --- основной алгоритм --- # получаем длину строки n = len(s) # здесь будет наш ответ res = 0 # перебираем символы от первого до последнего for i in range(n): # перебираем символы от текущего до последнего for j in range(i, n): # если в получившейся подстроке нет повторяющихся символов if check(i, j): # смотрим, максимальный ли это результат, и если да — запоминаем его res = max(res, j - i + 1) # выводим результат на экран print(res)Объединим обе части и получим готовый код:
# исходная строка s = 'abcabcdcc' # функция, которая проверит, есть ли в подстроке повторяющиеся символы # на вход отправляем начальную и конечную позицию в строке для проверки def check(start, end): # создаём пустое множество chars = set() # делаем цикл от начального до конечного символа for i in range(start, end + 1): # получаем очередной символ из строки c = s[i] # если символа уже есть в множестве if c in chars: # возвращаем False — в строке есть повторяющиеся символы return False # добавляем символ в множество chars.add(c) # если дошли досюда — возвращаем True return True # --- основной алгоритм --- # получаем длину строки n = len(s) # здесь будет наш ответ res = 0 # перебираем символы от первого до последнего for i in range(n): # перебираем символы от текущего до последнего for j in range(i, n): # если в получившейся подстроке нет повторяющихся символов if check(i, j): # смотрим, максимальный ли это результат, и если да — запоминаем его res = max(res, j - i + 1) # выводим результат на экран print(res)Хотите больше? Скачивайте наш гид
В нем мы собрали всё, что нужно знать о старте в сфере ИТ. Читайте на компьютере и телефоне, распечатывайте на принтере, пересылайте друзьям, используйте как учебное пособие в вузе и школе.
Гид скачивается бесплатно, без регистрации и ввода электронной почты. Просто тык и всё. Не забудьте сохранить на компьютере, если гид откроется в браузере.
Получите ИТ-профессию
В «Яндекс Практикуме» можно стать разработчиком, тестировщиком, аналитиком и менеджером цифровых продуктов. Первая часть обучения всегда бесплатная, чтобы попробовать и найти то, что вам по душе. Дальше — программы трудоустройства.
Поиск максимального значения в списке на Python
В этой статье мы научимся находить максимальное значение в списке на Python. Для всестороннего понимания вопроса мы рассмотрим использование некоторых встроенных функций, простые подходы, а также небольшие реализации известных алгоритмов.
Сначала давайте вкратце рассмотрим, что такое список в Python и как найти в нем максимальное значение или просто наибольшее число.
Список в Python
В Python есть встроенный тип данных под названием список (list). По своей сути он сильно напоминает массив. Но в отличие от последнего данные внутри списка могут быть любого типа (необязательно одного): он может содержать целые числа, строки или значения с плавающей точкой, или даже другие списки.
Хранимые в списке данные определяются как разделенные запятыми значения, заключенные в квадратные скобки. Списки можно определять, используя любое имя переменной, а затем присваивая ей различные значения в квадратных скобках. Он является упорядоченным, изменяемым и допускает дублирование значений. Например:
list1 = ["Виктор", "Артем", "Роман"] list2 = [16, 78, 32, 67] list3 = ["яблоко", "манго", 16, "вишня", 3.4]Далее мы рассмотрим возможные варианты кода на Python, реализующего поиск наибольшего элемента в списке, состоящем из сравниваемых элементов. В наших примерах будут использоваться следующие методы/функции:
- Встроенная функция max()
- Метод грубой силы (перебора)
- Функция reduce()
- Алгоритм Heap Queue (очередь с приоритетом)
- Функция sort()
- Функция sorted()
- Метод хвостовой рекурсии
№1 Нахождение максимального значения с помощью функции max()
Это самый простой и понятный подход к поиску наибольшего элемента. Функция Python max() возвращает самый большой элемент итерабельного объекта. Ее также можно использовать для поиска максимального значения между двумя или более параметрами.
В приведенном ниже примере список передается функции max в качестве аргумента.
Интересная задача в python? Решать нужно в цикле (for) без функций и методов! Можно использовать условные операторы!
Напишите программу, которая получает на вход строку, подсчитывает в ней самую длинную последовательность подряд идущих букв “s” и выводит ответ на экран.
Введите строку: ssbbbsssbc
Самая длинная последовательность: 3Голосование за лучший ответ
не, не особо интересная, через один while считается
Сергей ВилковУченик (86) 2 года назад
А без while?
viv2537 Оракул (87798) Сергей Вилков, через 2 forcount=0
result=0
for i in s:
~~if i=='s': count+=1
~~else:
~~~~if count>result: result=count; count=0
if count>result: result=count;
print (result)Veter .Мастер (1105) 2 года назад
А вот в таком случае ваша программа не работает
port port Искусственный Интеллект (181509) Veter ., Добавь перед print (result) if count>result: result=count
Сергей ВилковУченик (86) 2 года назад
Результат получается = 5, а это не правильно. Вы считаете общее количество "s", а не самую длинную её последовательность.
port port Искусственный Интеллект (181509) Сергей Вилков, Условие задачи поменялось на s='ssbbbsssbcsssss'
Сергей ВилковУченик (86) 2 года назад
И всё-равно вы считаете общую сумму "s", а в условие задачи нужно: подсчитывать самую длинную последовательность подряд идущих букв “s” и выводит ответ на экран?
port port Искусственный Интеллект (181509) Сергей Вилков, В s='ssbbbsssbcsssss' самая длинная последовательность s находится в конце строки и равна 5. Или я что-то путаю?
Что тут интересного? Если тебе нужно написать программу то просто иди в цикле for до конца строки и символы сравнивает
stroka = input()
counter = 1
max = 0
for i in range(1, len(stroka)):
____if stroka[i] == stroka[i-1] == 's':
________counter = counter + 1
________if counter > max:
____________max = counter
____else:
________counter = 1
print(max)Сергей ВилковУченик (86) 2 года назад
Я так и сам могу! Ты попробуй без: max, len, [ ] !
Сергей ВилковУченик (86) 2 года назад
А без len и [ i ] (без индексации)?Veter . Мастер (1105) Сергей Вилков, в смысле? А как обращаться к конкретному символу? Без этого никак
Сергей ВилковУченик (86) 2 года назад
Вот в этом то и дело (и вся сложность простой задачи), что нужно решить без этого!?
Сергей ВилковУченик (86) 2 года назадВот так можно переложить ваш код на простой "язык"!
print('Введите строку: ', end = '')
text = input()
text += ''
count_s = 0
letter = 0for symbol in text:
if symbol == 's':
letter += 1
else:
if letter > count_s:
count_s = letter
letter = 0
print('Самая длинная последовательность: ', count_s)Сергей Вилков, не работает, считает общее количество выбранного символа
string = input('Введите строку: ')
count = 0
result = 0for symbol in string:
~~if symbol == 's':
~~~~count += 1
~~elif count < result and symbol != 's':
~~~~count = 0
~~else:
~~~~if count > result:
~~~~~~result = count
~~~~~~count = 0
if count > result:
~~result = countprint('Самая длинная последовательность: ', result)
