GATTACA

Source file name: gattaca.c, gattaca.cpp or gattaca.java

The Institute of Bioinformatics and Medicine (IBM) of your country has been studying the
DNA sequences of several organisms, including the human one. Before analyzing the DNA of
an organism, the investigators must extract the DNA from the cells of the organism and decode
it with a process called “sequencing”.
A technique used to decode a DNA sequence is the “shotgun sequencing”. This technique is
a method applied to decode long DNA strands by cutting randomly many copies of the same
strand to generate smaller fragments, which are sequenced reading the DNA bases (A, C, G and
T) with a special machine, and re-assembled together using a special algorithm to build the
entire sequence.
Normally, a DNA strand has many segments that repeat two or more times over the sequence
(these segments are called “repetitions”). The repetitions are not completely identified by the
shotgun method because the re-assembling process is not able to differentiate two identical
fragments that are substrings of two distinct repetitions.
The scientists of the institute decoded successfully the DNA sequences of numerous bacterias
from the same family, with other method of sequencing (much more expensive than the shotgun
process) that avoids the problem of repetitions. The biologists wonder if it was a waste of
money the application of the other method because they believe there is not any large repeated
fragment in the DNA of the bacterias of the family studied.
The biologists contacted you to write a program that, given a DNA strand, finds the largest
substring that is repeated two or more times in the sequence.
Input
The first line of the input contains an integer T specifying the number of test cases (1>T<100).>n<1000).>

Sample input	Output for the sample input
56 GATTACA GAGAGAG GATTACAGATTACA TGAC TGTAC TTGGAACC	A 3 GAGAG 2 GATTACA 2 No repetitions found! T 2 A 2

Solucion

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.Map;
import java.util.TreeMap;
import java.util.logging.Level;
import java.util.logging.Logger;

public class gattacaV3 {

public static void main(String arg[]) {
File f = new File("gattaca.in");
try {
BufferedReader bf = new BufferedReader(new FileReader(f));
int numeroCasos = Integer.parseInt(bf.readLine());
String entrada = bf.readLine();
int testCase = 0;
while (entrada != null) {
String[] suffixes = getSuffixes(entrada);
String lrs = "";
int N = entrada.length(), repetitions = 2;
Map equalLength = new TreeMap();
for (int i = 0; i < N - 1; i++) {
String x = lcp(suffixes[i], suffixes[i + 1]);
if (x.length() > lrs.length()) {
lrs = x;
repetitions = 2;
equalLength = new TreeMap();
} else if (x.length() == lrs.length()) {
if (x.equals(lrs)) {
repetitions++;
equalLength.put(lrs, repetitions);
} else {
int currentCount = equalLength.get(x) != null ? equalLength.get(x) + 1 : 2;
if (equalLength.get(lrs) == null) {
equalLength.put(lrs, repetitions);
}
equalLength.put(x, currentCount);
}
}
}
String moreRepeated = "";
int maxRepetitions = 0;
for (Map.Entry entry : equalLength.entrySet()) {
if ("".equals(moreRepeated) || entry.getValue() > maxRepetitions) {
moreRepeated = entry.getKey();
maxRepetitions = entry.getValue();
}
}
if (!"".equals(moreRepeated)) {
lrs = moreRepeated;
repetitions = maxRepetitions;
}
if (!"".equals(lrs)) {
System.out.println(lrs + " " + repetitions);
} else {
System.out.println("No repetitions found!");
}
entrada = bf.readLine();
testCase++;
}
} catch (IOException ex) {
Logger.getLogger(gattaca.class.getName()).log(Level.SEVERE, null, ex);
}
}

public static String[] getSuffixes(String testCase) {
int N = testCase.length();
String[] suffixes = new String[N];
for (int i = 0; i < N; i++) {
suffixes[i] = testCase.substring(i, N);
}
Arrays.sort(suffixes);
return suffixes;
}

public static String lcp(String s, String t) {
int n = Math.min(s.length(), t.length());
for (int i = 0; i < n; i++) {
if (s.charAt(i) != t.charAt(i)) {
return s.substring(0, i);
}
}
return s.substring(0, n);
}
}