题目描述:
/**
牛牛又从生物科研工作者那里获得一个任务,
这次牛牛需要帮助科研工作者
从DNA序列s中找出最短没有出现在DNA序列s中的DNA片段的长度。
例如:s = AGGTCTA
序列中包含了所有长度为1的('A','C','G','T')片段,
但是长度为2的没有全部包含,
例如序列中不包含"AA",所以输出2。
输入描述:
输入包括一个字符串s,字符串长度length(1 ≤ length ≤ 2000),其中只包含'A','C','G','T'这四种字符。
输出描述:
输出一个正整数,即最短没有出现在DNA序列s中的DNA片段的长度。
输入例子1:
AGGTCTA
输出例子1:
2
*/
思路如下:
从片段长度为1开始
计算长度为d的片段(只计算片段不同的,相同片段不重复算)的数目
对于长度为len的字符串中d长度的片段只有
len-d+1个片段,而d长度的片段一共有2^d个排列的片段
len>=2^d+d-1
对于长度为len的字符串最多满足其长度为1 2 3 ...ceil(log(len))这些片段所有都取到
代码如下:
#include<stdio.h>
#include<iostream>
#include<set>
using namespace std;
int main()
{
string line;
cin>>line;
int targetNum=1;
for(int d=1; d<=line.size(); d++){
targetNum*=4;
set<string> cntSet;
for(int i=0; i<line.size(); i++){
if(i+d>=line.size())
break;
string subStr=line.substr(i, d);
cntSet.insert(subStr);
}
if(cntSet.size()<targetNum){
printf("%d", d);
break;
}
}
return 0;
}