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 11:18:26
Task:DNA sequence
Sender:Ace of Spades
Submission time:2016-05-28 11:18:26
Status:READY
Result:ACCEPTED

Show test data

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:29:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < s.size(); ++j) {
                                   ^

Code

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll MOD = 9876544324323121ll;
const int MN = 1e5+100;
const ll ha = 107;
char t[MN];
ll qwe[MN];
unordered_set<ll> st;
unordered_set<ll> st2;
int main(void) {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(12);
    int n,q;
    st.max_load_factor(0.5);
    st2.max_load_factor(0.5);
    string sss;
    cin>>sss;
    n = sss.size();
    for(int i = 0; i < n; ++i) {
        t[i] = sss[i];
    }
    cin>>q;
    for(int i = 0; i < q; ++i) {
        string s;
        cin>>s;
        for(int j = 0; j < s.size(); ++j) {
            qwe[i] = (qwe[i]*ha + s[j])%MOD;
        }
        st.insert(qwe[i]);
    }
    for(int i = 0; i < n; ++i) {
        ll hash = 0;
        for(int j = 0; i+j < n && j < 10; ++j) {
            hash = (hash*ha + t[i+j])%MOD;
            if(st.count(hash)) {
                st2.insert(hash);
            }
        }
    }
    for(int i = 0; i < q; ++i) {
        if(st2.count(qwe[i])) {
            cout<<"YES\n";
        }
        else {
            cout<<"NO\n";
        }
    }
    return 0;
}