Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.72/18: Рейтинг темы: голосов - 18, средняя оценка - 4.72
1 / 1 / 0
Регистрация: 28.06.2016
Сообщений: 80

Написать программу, которая выводит позиции всех вхождений гена в геном (поиск гена)

30.07.2016, 15:35. Показов 3833. Ответов 20
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Задан геном некоторого организма (последовательность букв A T G C (аденин, тимин, гуанин, цитозин). Также задан некоторый ген (тоже последовательность A T G C), который биологи пытаются найти в геноме организма. Требуется написать программу, которая выводит позиции всех вхождений гена в геном. Нумерация позиций начинается с нуля. Длина гена будет меньше длины генома.

Вход:
AGCTTATGCCAAGCTCTA
AGCT

AAAAAAAAAA
AAA

ATGTGTGTCAAT
TTT

ATGTGTGTCAAT
TGT

AGCTGCTA
A


Выход:
0 11
0 1 2 3 4 5 6 7
1 3 5
0 7
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
30.07.2016, 15:35
Ответы с готовыми решениями:

Написать программу, которая выводит на экран массив с указанной пользователем позиции
Одномерный динамический массив. Написать программу, которая выводит на экран массив с указанной пользователем позиции. Если позиция больше...

Гена vs. Чебурашка
Крокодил Гена с Чебурашкой играли в какую-то игру, выписывая числа в клетки квадратной таблицы n×n . Однако, когда таблица была...

Гена, Чебурашка, Шапокляк
Может быть эту задачу я разместил не в той теме, прошу поправить в таком случае. От дома крокодила гены к дому чебурашки проведен кабель...

20
2688 / 2260 / 244
Регистрация: 03.07.2012
Сообщений: 8,231
Записей в блоге: 1
06.08.2016, 06:17
Студворк — интернет-сервис помощи студентам
КМП идеально подходит:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// префикс-функция для алгоритма Кнута-Морриса-Пратта (КМП)
vector<int> prefix_function (string s) {
    int n = (int) s.length();
    vector<int> pi (n); // в i-м элементе (его индекс i-1) количество совпавших символов в начале и конце для построки длины i. 
                        //p[0]=0 всегда, p[1]=1, если начинается с двух одинаковых 
    for (int i=1; i<n; ++i) {
        int j = pi[i-1];
        while ((j > 0) && (s[i] != s[j])) // не равны
            j = pi[j-1];                // берем ранее рассчитанное значение (начиная с максимально возможных)
        if (s[i] == s[j]) // равны 
            ++j; 
        pi[i] = j;
     }
     return pi;
}
Для Си можно вместо вектора сделать массив и передавать его 2м параметром в функцию (не забыть обнулить pi[0] );
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
06.08.2016, 06:17

Заданы имена Валя,Гена,Женя....
Заданы имена Валя,Гена,Женя,Коля,Маша,Нина,Саша,Таня,Федя,Шура. Ввести массивы &quot;пол&quot; (Содержащий только два различных...

Крокодил Гена захотел выиграть в лотерею автомобиль
Крокодил Гена захотел выиграть в лотерею автомобиль. Для этого он накупил N лотерейных билетов, Чебурашка попросил поделиться с ним, потому...

Гена любит участвовать в соревнованиях на платформе iqpforces
Нужно сделать Ввод именно как сказано , то есть в одну строку через пробел.Как реализовать ? У меня получилось, только через enter. Вот мой...

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

Написать программу, которая выводит на экран список всех файлов
Написать программу, которая выводит на экран список всех файлов текущего каталога с датой и временем их последнего обновления.


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

Или воспользуйтесь поиском по форуму:
21
Ответ Создать тему
Новые блоги и статьи
Транслитерация текста с кириллицы на латиницу (вариант №5)
Maks 17.11.2026
Дабы оставить позади все споры о том, какая буква каким образом должна транслитерироваться на латиницу - решил таки доработать данное решение и довести его до мало-мальски логического завершения. . . .
Просмотровщик HLP и конвертер в CHM
Argus19 16.11.2026
Просмотровщик HLP и конвертер в CHM Давно хотел переделать справку Microsoft® Win32® Programmer's Reference, чтобы иметь её под рукой. Но использовать несколько программ не удобно. Искал другие. . .
BitTorrent (версия 7.11 English) и Меню Настройки
russiannick 15.11.2026
Пункты, отвечающие за отключение обновлений в BitTorrent версии 7. 11 (английской) Options Preferences General Language
Транслитерация текста с кириллицы на латиницу (вариант №4)
Maks 15.11.2026
Что-то я перемудрил с предыдущими версиями, в этот раз сделал всё проще, обратившись к функции "СтрокаЛатиницей" из типового общего модуля "СтроковыеФункцииКлиент". В данной функции нет апострофов,. . .
BitTorrent (версия 4.3.9) и Меню Настройки
russiannick 15.11.2026
В меню Настройки можно отключить автоматическое обновление программы. Карта этого меню приложена ниже. Нужный пункт выделен красным. Сервис Настройки Поведение
Транслитерация текста с кириллицы на латиницу (вариант №3)
Maks 15.11.2026
Обновленная версия предыдущей обработки. Изменения коснулись букв: Ъ, Ы, Ь, Э, отображения которых зависят от положения реквизита "Транслитерация имён". Изменено отображение буквы Й. Добавлена. . .
Транслитерация текста с кириллицы на латиницу (вариант №2)
Maks 13.11.2026
Обновленная версия ранее созданной обработки. Добавлено: - Проверка исходного текста на кириллицу, через обращение к стандартной функции "ТолькоКириллицаВСтроке" из общего модуля. . .
Часы с термометром и праздничным календарем
yariko 12.11.2026
Сегодня мы рассмотрим как можно сделать отличные многофункциональные часы. Итак, поставим конкретную задачу: разработать часы с календарем, двумя термодатчиками, выводом поздравительных сообщений. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru