[UVA][SA] 11512 - GATTACA
GATTACA
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''.
| GATTACA |
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
). Each test case consists of a single line of text that represents a DNA sequence S
of length n
(
1 n 1000
).
You can suppose that each sequence S
only contains the letters A, C, G and T.
Output
For each sequence in the input, print a single line specifying the largest substring of S that appears two or more times repeated in S , followed by a space, and the number of ocurrences of the substring in S .
If there are two or more substrings of maximal length that are repeated,
you must choose the least according to the lexicographic order.
If there is no repetition in S
, print ``No repetitions found!''
Sample Input
6 GATTACA GAGAGAG GATTACAGATTACA TGAC TGTAC TTGGAACC
Sample Output
A 3 GAGAG 2 GATTACA 2 No repetitions found! T 2 A 2
suffix array
建造高度數組, 求最高即可
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct SuffixArray {
int sa[1005], h[1005], n;
int w[1005], ta[1005], tb[1005];
char str[1005];
void sort(int *x, int *y, int m) {
static int i;
for(i = 0; i < m; i++)
w[i] = 0;
for(i = 0; i < n; i++)
w[x[y[i]]]++;
for(i = 1; i < m; i++)
w[i] += w[i-1];
for(i = n-1; i >= 0; i--)
sa[--w[x[y[i]]]] = y[i];
}
bool cmp(int *r, int a, int b, int l) {
if(r[a] == r[b]) {
if(a+l >= n || b+l >= n)
return false;
return r[a+l] == r[b+l];
}
return false;
}
void build_h() {
int i, j, k;
for(i = 0; i < n; i++) ta[sa[i]] = i;
for(i = 0; i < n; i++) {
if(ta[i] == 0) {
h[ta[i]] = 0;
continue;
}
if(i == 0 || h[ta[i-1]] <= 1)
k = 0;
else
k = h[ta[i-1]]-1;
while(str[sa[ta[i]-1]+k] == str[sa[ta[i]]+k])
k++;
h[ta[i]] = k;
}
}
void build() {// x: rank, y: second key
int i, k, m = 128, p;
int *x = ta, *y = tb, *z;
n = strlen(str);
x[n] = 0;
for(i = 0; i < n; i++)
x[i] = str[i], y[i] = i;
sort(x, y, m);
for(k = 1, p = 1; p < n; k *= 2, m = p) {
for(p = 0, i = n-k; i < n; i++)
y[p++] = i;
for(i = 0; i < n; i++) {
if(sa[i] >= k) {
y[p++] = sa[i]-k;
}
}
sort(x, y, m);
z = x, x = y, y = z;
for(i = 1, p = 1, x[sa[0]] = 0; i < n; i++)
x[sa[i]] = cmp(y, sa[i-1], sa[i], k) ? p-1 : p++;
}
}
};
int main() {
SuffixArray in;
int t;
scanf("%d", &t);
getchar();
while(t--) {
gets(in.str);
in.build();
in.build_h();
int ans = 0, anst = 0;
for(int i = 0; i < in.n; i++)
ans = ans > in.h[i] ? ans : in.h[i];
if(ans == 0) {
puts("No repetitions found!");
} else {
for(int i = 0; i < in.n; i++) {
if(ans == in.h[i]) {
for(int j = 0; j < ans; j++)
printf("%c", in.str[in.sa[i]+j]);
while(i < in.n && ans == in.h[i])
anst++, i++;
break;
}
}
printf(" %d\n", anst+1);
}
}
return 0;
}