Форум » Обработка символьных строк » №203 » Ответить
№203
Родион: Текстовый файл 24-203.txt содержит строку из заглавных латинских букв A, B и C, всего не более чем из 10^6 символов. Определите количество подстрок длиной не менее трех символов, которые не содержали бы одновременно все три буквы A, B и C. Примечание: подстрока — это непрерывный фрагмент исходной строки. file = open('24-203.txt').read() # Для упрощения скажем, что file = 'BCAABABABAACCABAAABBAABAAACAB' fileAB = file.replace('C', ' ').split(' ') # Массив подстрок, содержащих только символы А и В: ['B', 'AABABABAA', '', 'ABAAABBAABAAA', 'AB'] fileAC = file.replace('B', ' ').split(' ') # Только А и С: ['', 'CAA', 'A', 'A', 'AACCA', 'AAA', '', 'AA', 'AAACA', ''] fileBC = file.replace('A', ' ').split(' ') # Только В и С: ['BC', '', 'B', 'B', 'B', '', 'CC', 'B', '', '', 'BB', '', 'B', '', '', 'C', 'B'] s = 0 # Просто находим подстроки, длина которых не менее трёх и увеличиваем счётчик. for i in fileAB: if len(i) >= 3: s+=1 for i in fileAC: if len(i) >= 3: s+=1 for i in fileBC: if len(i) >= 3: s+=1 print(s) Результат: 29422 Ответ на сайте: 252776 Мне кажется, я не до конца понял условие...
Ответов - 3
Поляков: Пусть file = 'BCCCA'. Здесь 5 подходящих подстрок: BCC, BCCC, CCC, CCCA, CCA. Ваша программа дает ответ 2.
Volkoof: [pre2] s = open('24.txt').readline() ans = 0 def f(len_): global ans for i in range(len(s)): if len(set(map(str, s[ i:i+len_]))) < 3 and len(s[ i:i+len_])==len_: ans+=1 for i in range(3,33+1): f(i) print(ans) #ответ: 252776 [/pre2] range(3, 33+1) тк по условию длина самой маленькой допустимой строки является 3, длина наибольшей строки в файле - 33(найдено программно(ниже), но можно и руками перебрать) [pre2] s = open('24.txt').readline() j = 0; a = set(); b = [] def f(id): global j a.add(s[id]) if len(a)<3: j+=1; f(id+1) return j for i in range(0,len(s)-3): b.append(f(i)); j = 0; a.clear() print(max(b)) #ответ: 33 [/pre2]
gutgut: Не переборное (!) решение ну очень похожей задачи есть на сайте https://www.geeksforgeeks.org/count-of-sub-strings-that-do-not-contain-all-the-characters-from-the-set-a-b-c-at-the-same-time/ Простая (и очевидная) модификация приведенной там программы позволяет получить правильный ответ.
полная версия страницы