Code Submission Evaluation System Login

CSES - HIIT Open 2016

HIIT Open 2016

Contest start:2016-05-28 11:00:00
Contest end:2016-05-28 16:00:00

Task list | Submit code | Submissions | Messages | Scoreboard | Statistics


History
2016-05-28 14:53:39
2016-05-28 13:44:18
2016-05-28 13:44:03
2016-05-28 11:06:23
Task:DNA sequence
Sender:zah
Submission time:2016-05-28 14:53:39
Status:READY
Result:ACCEPTED

Show test data

Code

#include <iostream>
#include <map>

using namespace std;



int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    string dna;
    cin >> dna;
    int n=dna.size();
    int DNA[n];
    map<char,int> m;
    m['A']=4; m['C']=1; m['T']=2; m['G']=3;    
    short int t[1<<21]={};
    for (int i=0; i<n; ++i){
        DNA[i]=m[dna[i]];
    }
    for(int i=0; i<n; ++i){
        int h=0;
        for (int j=0; j<min(10, n-i-1); ++j){
            h+=DNA[i+j];
            t[h]=1;
            h*=4;
        }
        
            
    }
    int q;
    cin >> q;
    for(int i=0; i<q; ++i){
        string sas; 
        cin >> sas;
        int s=sas.size();
        int h=0;
        int ff=1;
        for (int j=0; j<min(s,10);++j){
            h+=m[sas[j]];
            if (t[h]==0){
                ff=0;
                break;
            }
            h*=4;      
        } 
        if (ff) cout << "YES\n";
        else cout << "NO\n";
    }

}