CSES - HIIT Open 2016 - Results
Submission details
Task:DNA sequence
Sender:Verto
Submission time:2016-05-28 14:04:27 +0300
Language:C++
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.45 sdetails

Code

#include <iostream>
#include <string>
#include <map>

using namespace std;

class Node {
public:
	map<char, Node*> kids;
	void add_subs(string subs) {
		if (subs.size() == 0)
			return;
		char head = subs[0];
		string rest = subs.substr(1);
		if (kids.find(head) == kids.end()) {
			kids[head] = new Node();
		}
		kids[head]->add_subs(rest);
	}
	bool search(string subs) {
		if (subs.size() == 0)
			return true;
		char head = subs[0];
		string rest = subs.substr(1);
		if (kids.find(head) == kids.end()) {
			return false;
		}
		return kids[head]->search(rest);
	}
	void debug(int dep = 0) {
		for (map<char,Node*>::iterator it = kids.begin(); it != kids.end(); it++) {
			cout << dep << " " << it->first << endl;
			it->second->debug(dep+1);
		}
	}
};

int main() {
	string s;
	cin >> s;
	int n;
	cin >> n;

	Node root;

	for (int i = 0; i < (int)s.size(); i++) {
		root.add_subs(s.substr(i, 10));
	}
	//root.debug();

	for(int i=0; i<n; i++) {
		string q;
		cin >> q;
		if(root.search(q))
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}
}

Test details

Test 1

Verdict: ACCEPTED

input
ACGCGGGCTCCTAGCGTTAGCAGTTGAGTG...

correct output
YES
YES
NO
NO
YES
...

user output
YES
YES
NO
NO
YES
...