Submission details
Task:DNA sequence
Sender:eax511
Submission time:2016-10-22 13:30:54 +0300
Language:C++
Status:READY
Result:
Test results
testverdicttime
#10.37 sdetails

Compiler report

input/code.cpp: In function 'void cnthash(std::string&, int)':
input/code.cpp:15:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(v.size()<l)return;
               ^
input/code.cpp:21:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=l;i<v.size();++i){
                        ^

Code

#include <set>
#include <string>
#include <iostream>
using namespace std;
typedef long long ll;
set<ll> h[10];
ll x=2452343;
ll mod=1e9+7;
ll rhash(std::string& v){
  ll h=0;
  for(auto& c : v)h*=x,h+=c,h%=mod;
  return h;
}
void cnthash(std::string& v,int l){
  if(v.size()<l)return;
  ll hh=0;
  ll p=1;
  for(int i=0;i<l;++i)p*=x,p%=mod;
  for(int i=0;i<l;++i)hh*=x,hh+=v[i],hh%=mod;
  h[l-1].emplace(hh);
  for(int i=l;i<v.size();++i){
    hh*=x;
    hh-=v[i-l]*p;
    hh+=v[i];
    hh%=mod;
    hh+=(hh>>63)&mod;
    h[l-1].emplace(hh);
  }
}

int main(){
  string v;
  cin>>v;
  for(int i=1;i<=10;++i)cnthash(v,i);
  int m;
  cin>>m;
  for(int i=0;i<m;++i){
    cin>>v;
    cout<<(h[v.size()-1].count(rhash(v))?"YES":"NO")<<'\n';
  }
  return 0;
}

Test details

Test 1

Verdict:

input
ACGCGGGCTCCTAGCGTTAGCAGTTGAGTG...

correct output
YES
YES
NO
NO
YES
...

user output
YES
YES
NO
NO
YES
...