CSES - HIIT Open 2016 - Results
Submission details
Task:DNA sequence
Sender:Verto
Submission time:2016-05-28 13:43:08 +0300
Language:Python2
Status:READY
Result:
Test results
testverdicttime
#1--details

Code

import sys
lines = sys.stdin.readlines()
lines = [l.strip() for l in lines]
s = lines[0]
n = int(lines[1])

# Make trie
class Node:
	def __init__(self, val, depth):
		self.val = val
		self.kids = {}
		self.depth = depth
	def add_kid(self, kval):
		if kval in self.kids:
			return self.kids[kval]
		else:
			kid = Node(kval, self.depth+1)
			self.kids[kval] = kid
			return kid

	def add_subs(self, subs):
		if not subs:
			return
		a, rest = subs[0], subs[1:]
		kid = self.add_kid(a)
		kid.add_subs(rest)
	def search(self, q):
		if not q:
			return True
		a, rest = q[0], q[1:]
		if a not in self.kids:
			return False
		return self.kids[a].search(rest)

T = Node("",0)
for i in range(len(s)):
	T.add_subs(s[i:i+10])

def is_yes(q):
	#return q in s
	return T.search(q)


for i in range(2,n+2):
	if is_yes(lines[i]):
		print "YES"
	else:
		print "NO"
	

Test details

Test 1

Verdict:

input
ACGCGGGCTCCTAGCGTTAGCAGTTGAGTG...

correct output
YES
YES
NO
NO
YES
...

user output
(empty)