We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
# Build the Trie
for i, pattern in enumerate(genes):
node = root
for char in pattern:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.output.append(i) # Store only the index of the pattern
# Build failure links using BFS
queue = deque([root])
while queue:
current_node = queue.popleft()
for key, child_node in current_node.children.items():
queue.append(child_node)
failure_node = current_node.failure_link
while failure_node and key not in failure_node.children:
failure_node = failure_node.failure_link
child_node.failure_link = failure_node.children[key] if failure_node else root
if child_node.failure_link:
child_node.output += child_node.failure_link.output
return root
def search_ac_table(text, ac_table, health, first, last):
current_state = ac_table # Start at the root of the Aho-Corasick Trie
total_health = 0
for char in text:
while current_state != ac_table and char not in current_state.children:
current_state = current_state.failure_link
if char in current_state.children:
current_state = current_state.children[char]
else:
current_state = ac_table
for gene_index in current_state.output:
if first <= gene_index <= last:
total_health += health[gene_index]
return total_health
if name == 'main':
input = sys.stdin.read
data = input().split()
n = int(data[0])
genes = data[1:n + 1]
health = list(map(int, data[n + 1:2 * n + 1]))
s = int(data[2 * n + 1])
ac_table = build_ac_table(genes)
unhealthiest, healthiest = sys.maxsize, -sys.maxsize
index = 2 * n + 2
for _ in range(s):
first = int(data[index])
last = int(data[index + 1])
d = data[index + 2]
index += 3
d_total_health = search_ac_table(d, ac_table, health, first, last)
unhealthiest = min(unhealthiest, d_total_health)
healthiest = max(healthiest, d_total_health)
print(unhealthiest, healthiest)
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Determining DNA Health
You are viewing a single comment's thread. Return to all comments →
python3 there are 3 test cases going to failed we are using "Aho-Corasick algorithm for multi-pattern matching" code be like:
import sys from collections import deque
class TrieNode: def init(self): self.children = {} self.failure_link = None self.output = []
def build_ac_table(genes): root = TrieNode()
def search_ac_table(text, ac_table, health, first, last): current_state = ac_table # Start at the root of the Aho-Corasick Trie total_health = 0 for char in text: while current_state != ac_table and char not in current_state.children: current_state = current_state.failure_link
if name == 'main': input = sys.stdin.read data = input().split()