首页 > 代码库 > poj 4092:牛仔裤
poj 4092:牛仔裤
poj 4092:牛仔裤
题目：
基因地理计划是IBM和美国国家地理学会的合作研究项目，用来分析来自于数十万的捐助者的DNA，来研究人类在地球上的迁移图。
作为一个IBM的研究者，你被要求写一个程序，来发现共性的DNA片段，用来和个人调查信息关联以确定新的遗传标记。
DNA碱基序列通过按顺序排列分子中发现的含氮碱基来记录。有四种碱基：腺嘌呤（A），胸腺嘧啶（T），鸟嘌呤（G）和胞嘧啶（C）。一个6碱基的DNA序列可以表示为TAGACC。
给定一组DNA的碱基序列，确定发生在所有序列中最长的一系列碱基。
一个正整数m（2<=m<=10）表示数据集中碱基序列个数
m行，每行包括一个含有60个碱基的序列
3 2 GATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA 3 GATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATA GATACTAGATACTAGATACTAGATACTAAAGGAAAGGGAAAAGGGGAAAAAGGGGGAAAA GATACCAGATACCAGATACCAGATACCAAAGGAAAGGGAAAAGGGGAAAAAGGGGGAAAA 3 CATCATCATCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC ACATCATCATAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AACATCATCATTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
no significant commonalities AGATAC CATCATCAT
解题方案：
我们先看子问题：
1）求两个字符串的所有公共子串？ 使用方案是动态规划建表，然后查找表收集所有的公共字符串
2）对字符串集合排序？ 使用的是 STL 中的 stable_sort 函数（参数1，参数2）
3）对两个有序集合求交集？ 使用的是归并思想求交集
然后我们在考虑我们的大问题
对一组数据 ，使其随意两两组合求一组所有公共子串，如果字符串个数为奇数，则最后一个字符串和其他任意一个字符串组合
对每一组所有公共子串排序
对全部组所有公共子串进行任意两两组合求交集，如果公共子串组数为奇数，方法同上
迭代上一步，直至求出所有组的公共子串组，然后找出最长的一个即可（如果存在多个，则输出第一个即可，此时已是排好序的）
实验数据
3 2 GATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA 3 GATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATA GATACTAGATACTAGATACTAGATACTAAAGGAAAGGGAAAAGGGGAAAAAGGGGGAAAA GATACCAGATACCAGATACCAGATACCAAAGGAAAGGGAAAAGGGGAAAAAGGGGGAAAA 3 CATCATCATCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC ACATCATCATAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AACATCATCATTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
实验结果
代码
#include <iostream>
#include <string>
#include <list>
#include <algorithm>
#include <fstream>
#include <map>
using namespace std;
int const ELEM_LENGTH = 60;
typedef list<string>* Elem;
typedef Elem* TABLE;
// 根据动态表，建立对应长度的哈希表
void get_table(int ** data,int row,int column,TABLE & table,string a);
// 求出两个字符串的公共字串动态表
void common_substring(string a,string b,int ** &data,int &row,int &column);
// 读出所有数据，然后放在data二维数组中
void read_data();
// 主要解决方案
void main_solution(string * data,int m);
// 求交集
list<string> common_two_list(list<string> * list1,list<string> * list2);
// 求出两个字符串的公共字串动态表
void common_substring(string a,string b,int ** &data,int &row,int &column)
{
row = a.length()+1;
column = b.length()+1;
data = http://www.mamicode.com/new int *[row];>
poj 4092:牛仔裤
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。