[백준] 10256 돌연변이

문제

인간의 DNA 구조는 A, C, G, T로 이루어진 하나의 긴 문자열로 표현할 수 있다.

이때, 몇 몇 질병은 DNA 구조를 나타낸 문자열의 어떤 연속된 부분 문자열과 관련이 있다는 것이 밝혀져 있다. 만일 DNA가 특정 문자열을 부분 문자열로 가진다면 그 질병에 걸릴 가능성이 높다는 것이다. 이러한 특정 문자열을 마커(marker)라 한다.

하지만 때때로 DNA 구조를 그대로 확인하는 것만으로는 질병과 관련된 마커를 확인할 수 없는 경우가 있다. 마커의 돌연변이 가능성 때문이다.

마커의 돌연변이는 아래와 같이 일어난다.

• 먼저, 마커를 세 부분으로 나눈다, 이때, 첫 부분과 세 번째 부분은 비어 있어도 된다.
• 두 번째 부분을 뒤집는다.

예를 들어 마커가 AGGT라면 아래와 같은 여섯 가지 경우가 가능하다.

GAGT, GGAT, TGGA, AGGT, ATGG, AGTG

어떤 사람의 DNA 구조와 마커가 주어졌을 때, DNA 내에 마커가 돌연변이의 형태를 포함하여 몇 번 출현하는지 세는 프로그램을 작성하라.

단, 마커의 출현 위치는 서로 겹쳐도 된다. 예를 들어 DNA 구조가 ATGGAT이며 마커가 AGGT라면 답은 3이 된다. ATGG, TGGA, GGAT가 한 번씩 출현하기 때문이다.

 

입력

첫 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 줄엔 두 개의 정수 n과 m이 주어진다. 이는 각각 DNA 문자열의 길이와 마커의 길이이다. (1 ≤ n ≤ 1,000,000, 1 ≤ m ≤ 100) 두 번째 줄엔 DNA 구조가 주어진다. 마지막 줄엔 마커가 주어진다.

모든 DNA와 마커는 A,G,T,C로만 이루어진 문자열이다.

출력

각 테스트 케이스마다 주어진 DNA 구조에 마커와 그 돌연변이가 몇 번 출현하는지 하나의 정수로 출력한다.

만일 DNA 구조 내에 마커 또는 그 돌연변이가 한 번도 출현하지 않는다면 답은 0이 된다.

 

 

어떤 DNA마커에 대해 돌연변이를 만들어야합니다.

기준을 잡고 뒤집어야하는데, string에대해 reverse함수를 사용합니다.

 

reverse(iter, iter+k)는 iter부터 iter+k-1까지 뒤집어집니다.

  for (int i = 0; i < M; i++) {
            for (int j = i + 1; j < M; j++) {
                string s = marker;
                reverse(s.begin() + i, s.begin()+1+j);
                root->insert(s.c_str());
            }
        }

이렇게 뒤집어진 돌연변이들이 DNA에 몇개 존재하는지 확인하면 됩니다.

따라서 다대일패턴매칭 문제입니다.

아호코라식 알고리즘을 사용합니다.

 

모든 돌연변이들을 트라이에 넣고 정답을 출력합니다.

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 }, INF = 987654321;

// 트라이 구조체
int ret(char c) {
    if (c == 'A')return 0;
    if (c == 'G')return 1;
    if (c == 'C')return 2;
    if (c == 'T')return 3;
}
struct Trie {
    Trie* go[4];
    Trie* fail;
    bool output;


    Trie() {
        fill(go, go + 4, nullptr);
        output = false;

    }
    ~Trie() {
        rep(i, 4)
            if (go[i])delete go[i];
    }
    void insert(const char * key) {
        if (!*key) {
            output = true;
            return;
        }
        int next = ret(*key);
        if (!go[next]) {
            go[next] = new Trie;
        }
        go[next]->insert(key + 1);
    }
};
int TC, N, M;
int main() {
    FAST;
    cin >> TC;
    while (TC--) {
        cin >> N >> M;
        string DNA, marker;
        cin >> DNA >> marker;
        //돌연변이
        //루트
        Trie* root = new Trie;
        //루트에 삽입
        root->insert(marker.c_str());
        for (int i = 0; i < M; i++) {
            for (int j = i + 1; j < M; j++) {
                string s = marker;
                reverse(s.begin() + i, s.begin()+1+j);
                root->insert(s.c_str());
            }
        }
        queue<Trie*>q;
        root->fail = root;

        //BFS를 이용해 fail
        q.push(root);
        while (!q.empty()) {
            auto cur = q.front();
            q.pop();
            rep(i, 4) {
                Trie* next = cur->go[i];
                if (!next)continue;

                if (cur == root) next->fail = root;
                else {
                    Trie* back = cur->fail;
                    while (back != root && !back->go[i]) {
                        back = back->fail;
                    }
                    if (back->go[i])
                        back = back->go[i];
                    next->fail = back;
                }
                if (next->fail->output)
                    next->output = true;
                q.push(next);
            }
        }
        //한 문자씩 검사
        Trie* cur = root;
        int ans = 0;
        for (char c : DNA) {
            int next = ret(c);
            while (cur != root && !cur->go[next]) {
                cur = cur->fail;
            }
            if (cur->go[next])cur = cur->go[next];

            //만약 끝자리라면
            if (cur->output) {
                ans++;
            }
        }
        cout << ans << "\n";
        delete root;
    }
}