24h購物| | PChome| 登入
2013-12-28 20:39:04| 人氣1,967| 回應0 | 上一篇 | 下一篇

[数据结构与算法] 第14周 高级数据结构（2）

推薦 0 收藏 0 轉貼0 訂閱站台

1:牛奶模式


描述

农场主约翰注意到他家奶牛提供的牛奶质量每天各不相同。通过进一步调查，他发现尽管他不能通过一天的牛奶质量预测下一天，但是每天的牛奶质量存在规律。

为了进行严密的研究，他发明了一个复杂的分类机制，将牛奶样本记录为一个0到1,000,000（含0和1,000,000）的整数。而且，他记录了一头奶牛N天（1<=N<=20,000）的数据。他希望找到重复K次（2<=K<=N）的最长的模式。这可能包括重叠的模式——比如1 2 3 2 3 2 3 1 重复了2 3 2 3两次。

请帮助约翰找到样例序列中的最长的重复子序列。数据保证至少存在一个子序列重复了至少K次。


输入
第1行：用空格分隔的两个整数：N和K
第2到N+1行：N个整数，一个一行，第i天的牛奶质量由其中的第i行表示
输出
一行：一个整数，表示重复至少K次的最长模式的长度
样例输入
8 2
1
2
3
2
3
2
3
1
样例输出
4

後綴數組建造高度數組，二分搜尋掃描高度數組即可。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
struct SuffixArray {
    int sa[20005], h[20005], n;
    int w[20005], ta[20005], tb[20005];
    int str[20005];
    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 = n, p;
        int *x = ta, *y = tb, *z;
        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 N, K;
    int i, j, k;
    while(scanf("%d %d", &N, &K) == 2) {
        for(i = 0; i < N; i++)
            scanf("%d", &in.str[i]);
        in.n = N;
        std::pair<int, int> d[20005];
        for(i = 0; i < N; i++)
            d[i] = std::make_pair(in.str[i], i);
        std::sort(d, d+N);
        int counter = 0;
        for(i = 0; i < N; i++) {
            if(i == 0 || d[i].first != d[i-1].first)
                counter++;
            in.str[d[i].second] = counter;
        }
        in.build();
        in.build_h();
        int l = 0, r = N, mid;
        int ret = 0;
        while(l <= r) {
            mid = (l+r)/2;
            int flag = 0;
            counter = 0;
            for(i = 0; i < N; i++) {
                if(in.h[i] >= mid)
                    counter++;
                else {
                    if(counter+1 >= K) {
                        flag = 1;
                        break;
                    }
                    counter = 0;
                }
            }
            if(counter+1 >= K)    flag = 1;
            if(flag) {
                l = mid+1;
                ret = mid;
            } else {
                r = mid-1;
            }
        }
        printf("%d\n", ret);
    }
    return 0;
}

2:牛仔裤


描述

基因地理计划是IBM和美国国家地理学会的合作研究项目，用来分析来自于数十万的捐助者的DNA，来研究人类在地球上的迁移图。

作为一个IBM的研究者，你被要求写一个程序，来发现共性的DNA片段，用来和个人调查信息关联以确定新的遗传标记。

DNA碱基序列通过按顺序排列分子中发现的含氮碱基来记录。有四种碱基：腺嘌呤（A），胸腺嘧啶（T），鸟嘌呤（G）和胞嘧啶（C）。一个6碱基的DNA序列可以表示为TAGACC。

给定一组DNA的碱基序列，确定发生在所有序列中最长的一系列碱基。


输入
输入以一个整数n作为单独的一行来开头，表示数据集个数。每个数据集包括以下成分：
一个正整数m（2<=m<=10）表示数据集中碱基序列个数
m行，每行包括一个含有60个碱基的序列
输出
对于每一个数据集，输出所有碱基序列中共同的最长的子碱基序列。如果这个最长的共同碱基子序列比三要小，则输出”no significant commonalities”以代替。如果存在多个相同长度的最长共同碱基子序列存在，则只输出按字母顺序排列的第一个序列。
样例输入
3
2
GATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
3
GATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATA
GATACTAGATACTAGATACTAGATACTAAAGGAAAGGGAAAAGGGGAAAAAGGGGGAAAA
GATACCAGATACCAGATACCAGATACCAAAGGAAAGGGAAAAGGGGAAAAAGGGGGAAAA
3
CATCATCATCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
ACATCATCATAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AACATCATCATTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
样例输出
no significant commonalities
AGATAC
CATCATCAT
後綴數組建造高度數組，二分搜尋掃描高度數組即可。

其中要將所有字串做相接動作，並且每個字串間要填入額外的字元，不可與原本的重複。

O(n log n)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
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;
        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 testcase, n, m;
    int i, j, k;
    char s[128];
    int A[1005];
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &n);
        int idx = 0;
        for(i = 0; i < n; i++) {
            scanf("%s", s);
            for(j = 0; s[j]; j++) {
                A[idx] = i;
                in.str[idx++] = s[j];
            }
            A[idx] = -1;
            in.str[idx++] = 'a' + i;
        }
        in.str[idx] = '\0';
        in.n = strlen(in.str);
        in.build();
        in.build_h();
        /*printf("%s %d\n", in.str, in.n);
        for(i = 0; i < in.n; i++)
            printf("%s %d\n", in.str+in.sa[i], in.sa[i] >= 0 ? A[in.sa[i]] : -1);*/
        int l = 0, r = in.n, mid;
        int ret = 0, ret_startIdx;
        while(l <= r) {
            mid = (l+r)/2;
            int flag = 0, startIdx;
            int    counter[20] = {}, diff = 0;
            for(i = 0; i <= in.n; i++) {
                if(i != in.n && in.h[i] >= mid) {
                    if(i && A[in.sa[i-1]] >= 0) {   
                        if(counter[A[in.sa[i-1]]] == 0)
                            diff++;
                        counter[A[in.sa[i-1]]]++;
                    }
                } else {
                    if(i && in.h[i-1] >= mid) {
                        if(A[in.sa[i-1]] >= 0) {   
                            if(counter[A[in.sa[i-1]]] == 0)
                                diff++;
                            counter[A[in.sa[i-1]]]++;
                        }                   
                        if(diff == n) {
                            flag = 1;
                            startIdx = in.sa[i-1];
                            break;
                        }
                    }
                    if(diff) {
                        for(j = 0; j < n; j++)
                            counter[j] = 0;
                        diff = 0;           
                    }
                }
            }
            if(flag) {
                l = mid+1;
                ret = mid;
                ret_startIdx = startIdx;
                //printf("search %s %d\n", in.str + startIdx, ret);
            } else {
                r = mid-1;
            }
        }
        if(ret < 3)
            puts("no significant commonalities");
        else {
            for(i = 0; i < ret; i++)
                printf("%c", (in.str + ret_startIdx)[i]);
            puts("");
        }
    }
    return 0;
}
/*
3
2
GATACCAGATACCA
AAAAAAAAAAAAAA
3
GATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATA
GATACTAGATACTAGATACTAGATACTAAAGGAAAGGGAAAAGGGGAAAAAGGGGGAAAA
GATACCAGATACCAGATACCAGATACCAAAGGAAAGGGAAAAGGGGAAAAAGGGGGAAAA
*/

我要檢舉
#後綴數組#suffix array
台長： Morris

您可能對以下文章有興趣

人氣(1,967) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 教育學習(進修、留學、學術研究、教育概況) | 個人分類: 其他題目 |
此分類下一篇:[高等演算法] 雜II
此分類上一篇:[数据结构与算法] 第13周 高级数据结构（1）

我要回應
否 是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼：
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文