Algoogle

Algorithm for Programming Contest

JOI 春合宿 2010 DNA Synthesizer

Category: JOI Tag: aho-corasick, dp

DNA Synthesizer

問題概要


DNAはATGCの4つの文字から成る.
今N個の素DNAがある(長さはそれぞれ高々20).
あるDNAを作りたいとき, 素DNA同士を長さ1以上重なるようにつなげることで作ることができる.
素DNAはそれぞれ何個でも使える.
最小何個の素DNAで目的のDNAを作れるか.

解法


Aho-Corasick法で目的のDNAの各位置でパターン(素DNA)とマッチするかみる.
このときマッチするもののうち, 最長のものだけ見れば良い.
あとはDPすればよい.
dp[i] := i文字目までつくるのに必要な最小の素DNAの数
更新はマッチした部分の中でdpが最小になっている部分+1でできる.
これはSegment-Treeを用いることで効率的にできるが, 今回はパターンの長さが高々20なので愚直に更新してもよい.

コード


(dna.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
const string dna = "aATGC";

struct PMA
{
        PMA* next[5];
        int matched;
        PMA(){ memset(next, 0, sizeof(next)); matched = -1;}
        ~PMA(){ for(int i = 0; i < 256; i++) if(next[i]) delete next[i];}
};

PMA *buildPMA(vector<string> &pattern)
{
        PMA *root = new PMA, *now;
        root->next[0] = root;
        int i = 0;
        for(string pat: pattern) {
                now = root;
                for(char c: pat) {
                        int p = dna.find(c);
                        if(now->next[p] == 0)
                                now->next[p] = new PMA;
                        now = now->next[p];
                }
                int &mt = now->matched;
                if(mt < 0 or pattern[mt].size() < pat.size()) mt = i;
                i++;
        }

        queue<PMA*> que;
        for(i = 1; i < 5; i++){
                if(!root->next[i]) root->next[i] = root;
                else {
                        root->next[i]->next[0] = root;
                        que.push(root->next[i]);
                }
        }
        while(!que.empty()){
                now = que.front(); que.pop();
                for(i = 1; i < 5; i++){
                        if(now->next[i]){
                                PMA *nxt = now->next[0];
                                while(!nxt->next[i]) nxt = nxt->next[0];
                                now->next[i]->next[0] = nxt->next[i];
                                int &mt1 = now->next[i]->matched, &mt2 = nxt->next[i]->matched;
                                if(mt1 < 0 or (~mt2 and pattern[mt1].size() < pattern[mt2].size())) mt1 = mt2;
                                que.push(now->next[i]);
                        }
                }
        }
        return root;
}

int n, m, dp[150010];
string s;
vector<string> pat;

int solve()
{
        m = s.size();
        PMA* pma = buildPMA(pat);
        fill(dp,dp+m,inf);
        dp[0] = 0;
        for(int i = 0; i < m; i++){
                int c = dna.find(s[i]);
                while(!pma->next[c]) pma = pma->next[0];
                pma = pma->next[c];
                if(~pma->matched)
                        for (int j = 1; j < (int)pat[pma->matched].size(); j++)
                                dp[i] = min(dp[i], dp[i-j]+1);
        }
        return dp[m-1];
}

void input()
{
        cin >> n >> s;
        pat.resize(n);
        for (int i = 0; i < n; i++) cin >> pat[i];
}

int main()
{
        cin.tie(0);
        cin.sync_with_stdio(0);
        input();
        cout << solve() << endl;
        return 0;
}

Comments