(10256) 돌연변이

https://www.acmicpc.net/problem/10256

단계별로 풀어보기

46단계(문자열 알고리즘 1) 9번째

 

 

 

어떤 마커와 그 돌연변이 전부에 대해 일치하는 부분문자열의 수를 찾아야 하므로 일대다 매칭 알고리즘인 아호코라식을 써야 한다.

단 일치하는 모든 문자열의 수를 구해야 하므로 finish를 bool이 아닌 int로 선언하고, insert함수로 문자열을 집어넣을 때마다 마지막 노드의 finish를 1로 설정한다(중복되는 문자열이 나올 수 있는데 이 경우에도 하나로 세야 하기 때문). 이후 실패함수를 구성하면서 실패함수의 finish값을 더해주며 해당 노드의 문자열에서 겹치는 돌연변이 문자열을 전부 카운팅하고, DNA문자열이 끝날 때까지 실패 함수를 타고 계속 넘어가며 모든 일치하는 돌연변이를 찾아준다.

트라이의 다음 글자를 나타내는 go배열을 DNA에서 가능한 4글자만 담은 배열로 최적화했으며, 여러 테스트케이스로 이루어진 문제라 초기화나 메모리 누수에도 주의해야 한다.

 

 

 

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

inline int ACGT(char c){
  switch(c){
    case 'A': return 0;
    case 'C': return 1;
    case 'G': return 2;
    case 'T': return 3;
    default: return 4;
  }
}

struct Trie {
  int finish= 0;
  Trie* go[4]= {nullptr, };
  Trie* fail;
  ~Trie() { for(int i=0;i<4;i++)  if(go[i]!=nullptr)  delete go[i]; }
  
  void insert(string_view s){
    Trie* cur= this;
    
    for(char c:s){
      int x= ACGT(c);
      
      if(cur->go[x]==nullptr)  cur->go[x]= new Trie;
      
      cur= cur->go[x];
    }
    
    cur->finish= 1;
  }
  
  int find(string_view s){
    Trie* cur= this;
    int cnt= 0;
    
    for(char c:s){
      int x= ACGT(c);
      
      while(cur!=this&&cur->go[x]==nullptr)  cur= cur->fail;
      
      if(cur->go[x]!=nullptr)  cur= cur->go[x];
      if(cur->finish){
        cnt+= cur->finish;
      }
    }
    
    return cnt;
  }
  
  void init(){
    Trie* root= this;
    queue<Trie*> q;
    root->fail= root;
    q.push(root);
    
    while(!q.empty()){
      Trie* now= q.front();
      q.pop();
      
      for(int i=0;i<4;i++){
        Trie* next= now->go[i];
        
        if(next==nullptr)  continue;
        
        if(now==root){
          next->fail= root;
        }else{
          Trie* dest= now->fail;
          
          while(dest!=root&&dest->go[i]==nullptr)  dest= dest->fail;
          
          if(dest->go[i]!=nullptr)  dest= dest->go[i];
          next->fail= dest;
        }
        
        if(next->fail->finish)  next->finish+= next->fail->finish;
        
        q.push(next);
      }
    }
  }
};

void solve(){
  int n, m;
  string dna, marker;
  Trie* root= new Trie;
  
  cin >> n >> m >> dna >> marker;
  
  root->insert(marker);
  
  for(int i=0;i<m;i++){
    for(int j=i+1;j<m;j++){
      string mut= marker;
      reverse(mut.begin()+i, mut.begin()+j+1);
      
      root->insert(mut);
    }
  }
  
  root->init();
  
  cout << root->find(dna) << "\n";
  
  delete root;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int T;
  
  cin >> T;
  
  while(T--){
    solve();
  }
  
  return 0;
}