(9250) 문자열 집합 판별

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

단계별로 풀어보기

60단계(문자열 알고리즘 2) 9번째

 

 

 

일대다 매칭 알고리즘 아호 코라식에 대해 배우는 문제.

이전에 배운 트라이 자료구조를 사용한다. 일대일 매칭 알고리즘인 KMP를 일대다 매칭으로 확장한 듯한 알고리즘인데, KMP처럼 실패 함수를 이용해 문자열이 존재하는지 선형 시간으로 빠르게 찾아내는 알고리즘이다. 트라이 상의 어떤 노드에서 더 이상 다음 노드에 다음 문자열과 일치하는 문자가 없다 하더라도 처음으로 돌아가는 대신 지금까지 일치한 정보를 이용해야 하는데, 이때 실패 함수을 통해 최적의 노드로 이동하는 것이다. 더 정확히 말해 fail(x)=y라면 노드 x가 나타내는 문자열의 가장 긴 접미사를 나타내는 노드가 y다. y와도 일치하지 않으면 y의 실패함수로 가고, 이런 식으로 KMP처럼 반복하며 선형 시간 안에 탐색할 수 있는 것이다.

트라이를 만든 뒤 BFS로 순회하며 모든 노드의 실패 함수를 만든다. 이후 Q개의 검색하려는 문자열마다 트라이 및 실패 함수를 타고 트라이의 노드를 이동하다가 방문한 노드가 어떤 문자열의 끝이라면(finish가 true라면) 부분문자열이 존재하므로 참을 반환하고, 끝까지 찾지 못하면 거짓을 반환한다.

 

 

 

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

struct Trie {
  bool finish= false;
  Trie* go[26]= {nullptr, };
  Trie* fail;
  ~Trie() { for(int i=0;i<26;i++)  if(go[i]!=nullptr)  delete go[i]; }
  
  void insert(string_view s){
    Trie* cur= this;
    
    for(char c:s){
      int x= c-'a';
      
      if(cur->go[x]==nullptr)  cur->go[x]= new Trie;
      
      cur= cur->go[x];
    }
    
    cur->finish= true;
  }
  
  bool find(string_view s){
    Trie* cur= this;
    
    for(char c:s){
      int x= c-'a';
      
      while(cur!=this&&cur->go[x]==nullptr)  cur= cur->fail;
      
      if(cur->go[x]!=nullptr)  cur= cur->go[x];
      if(cur->finish)  return true;
    }
    
    return false;
  }
};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, m, ans= 0;
  Trie* root= new Trie();
  
  cin >> n;
  
  while(n--){
    string s;
    
    cin >> s;
    
    root->insert(s);
  }
  
  queue<Trie*> q;
  root->fail= root;
  q.push(root);
  
  while(!q.empty()){
    Trie* now= q.front();
    q.pop();
    
    for(int i=0;i<26;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= true;
      
      q.push(next);
    }
  }
  
  cin >> m;
  
  while(m--){
    string s;
    
    cin >> s;
    
    cout << (root->find(s) ? "YES\n" : "NO\n");
  }
  
  return 0;
}