實機體驗,再天天抽M8直擊★美車模手癢不小心...吉隆坡最便宜行程一覽表籌400萬醫藥費 俞嫻...
2013-03-03 16:07:57 人氣(26) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA][SA] 11107 - Life Forms

0
收藏
0
推薦

Problem C: Life Forms

You may have wondered why most extraterrestrial life forms resemble humans, differing by superficial traits such as height, colour, wrinkles, ears, eyebrows and the like. A few bear no human resemblance; these typically have geometric or amorphous shapes like cubes, oil slicks or clouds of dust.

The answer is given in the 146th episode of Star Trek - The Next Generation, titled The Chase. It turns out that in the vast majority of the quadrant's life forms ended up with a large fragment of common DNA.

Given the DNA sequences of several life forms represented as strings of letters, you are to find the longest substring that is shared by more than half of them.

Standard input contains several test cases. Each test case begins with 1 ≤ n ≤ 100, the number of life forms. n lines follow; each contains a string of lower case letters representing the DNA sequence of a life form. Each DNA sequence contains at least one and not more than 1000 letters. A line containing 0 follows the last test case.

For each test case, output the longest string or strings shared by more than half of the life forms. If there are many, output all of them in alphabetical order. If there is no solution with at least one letter, output "?". Leave an empty line between test cases.

Sample Input

3
abcdefg
bcdefgh
cdefghi
3
xxx
yyy
zzz
0

Output for Sample Input

bcdefg
cdefgh

?



錯誤的代碼一直過,真令人畏懼。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct SuffixArray {
    int sa[110005], h[110005], n;
    char str[110005];

    int w[110005], ta[110005], tb[110005]; // buffer
    void sort(int *x, int *y, int m) { // radix sort
        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(array index)
        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++;
        }
    }
};
SuffixArray SA;
int Sfrom[110005], Wlen[105], n, half;
char mark[105];
int check(int len, int printflag) {
    int i, j, k, cnt;
    for(i = n; i < SA.n; i++) {
        if(SA.h[i] >= len) {
            memset(mark, 0, sizeof(mark));
            j = i;
            cnt = 1;
            mark[Sfrom[SA.sa[i-1]]] = 1;
            while(j < SA.n && SA.h[j] >= len) {
                if(Sfrom[SA.sa[j]] != Sfrom[SA.sa[j]+len-1]) {
                    j++;break;
                }
                if(mark[Sfrom[SA.sa[j]]] == 0) {
                    mark[Sfrom[SA.sa[j]]] = 1;
                    cnt++;
                }
                j++;
            }
            if(cnt > half) {
                if(printflag) {
                    for(k = 0; k < len; k++)
                        putchar(SA.str[SA.sa[i]+k]);
                    puts("");
                } else {
                    return 1;
                }
            }
            i = j-1;
        }
    }
    return 0;
}
int main() {
    int i, first = 0;
    while(scanf("%d", &n) == 1 && n) {
        if(first)   puts("");
        first = 1;
        int m = 0;
        half = n/2; // > half
        int mxlen = 0;
        for(i = 0; i < n; i++) {
            scanf("%s", SA.str+m);
            int cnt = 0;
            while(SA.str[m])    Sfrom[m] = i, m++, cnt++;
            if(cnt > mxlen) mxlen = cnt;
            Wlen[i] = cnt;
            SA.str[m++] = '$';
            SA.str[m] = 0;
        }
        SA.str[m-1] = '\0';
        if(n == 1) {
            puts(SA.str);
            continue;
        }
        //puts(SA.str);
        SA.build();
        SA.build_h();
        int l = 1, r = mxlen;
        int res = 0;
        while(l <= r) {
            m = (l+r)/2;
            if(check(m, 0)) {
                l = m+1;
                if(m > res)
                    res = m;
            } else {
                r = m-1;
            }
        }
        if(res == 0)
            puts("?");
        else
            check(res, 1);
    }
    return 0;
}

11107Life Forms後綴數組Suffix ArraySA
台長:Morris
人氣(26) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][字串處理] 11048 - Automatic Correction of Misspellings
此分類上一篇:[UVA][dp][第二種] 10149 - Yahtzee

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文