LA 3527

From Algorithmist
Jump to: navigation, search

LA 3527 - Find the Clones[edit]

Summary[edit]

You are given a set of DNA sequences. The task is to find duplicates and make some statistics about them.

Explanation[edit]

The optimal solution is to build a trie containing all DNA sequences from the input. However, hashing or efficient sorting of the strings will work, too.

Input[edit]

9 6
AAAAAA
ACACAC
GTTTTG
ACACAC
GTTTTG
ACACAC
ACACAC
TCCCCC
TCCCCC

Output[edit]

1
2
0
1
0
0
0
0
0