爱奇艺 DNA序列 字符串

题目描述

牛牛又从生物科研工作者那里获得一个任务,这次牛牛需要帮助科研工作者从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

输出

2

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<set>
using namespace std;
const int maxn = 2e3+5;
string str;
int power(int a,int b)
{
    int ans=1;
    for(;b;b>>=1)
    {
        if(b&1) ans=(long long)ans*a;
        a=(long long)a*a;
    }
    return ans;
}
int main()
{
    while(cin>>str)
    {
        int len = str.length();
        for(int i=1;i<=len;++i)
        {
            set<string> m;
            int j;
            for(j=0;i+j<=len;++j)
            {
                m.insert(str.substr(j,i));
            }
            if(m.size()<power(4,i))
            {
                //cout<<m.size()<<"   !!!"<<endl;
                cout<<i<<endl;
                break;
            }
        }
        //set<string> :: iterator it;
        /* test sub string
        for(it=m.begin();it!=m.end();it++)
        {
            cout<<*it<<endl;
        }*/
        //it=m.begin();
        /*
        for(int i=1;i<=15;++i)
        {
            int cnt=0;
            string s2;
            for(it=m.begin();it!=m.end();it++)
            {
                s2=*it;
                if(s2.length()==i)
                {
                    cnt++;
                }
            }
            if(cnt!=power(4,i))
            {
                cout<<i<<endl;
                break;
            }
        }*/
    }
    return 0;
}