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:04:27
2016-05-28 13:43:08
2016-05-28 11:55:22
2016-05-28 11:33:56
Task:DNA sequence
Sender:Verto
Submission time:2016-05-28 14:04:27
Status:READY
Result:ACCEPTED

Show test data

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;
	}
}