(2809) 아스키 거리

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

단계별로 풀어보기

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

 

 

 

아호코라식으로 묶음 타일의 문자열이 존재하는 범위를 찾아 거리의 타일에서 아무런 매칭이 되지 않은 문자의 수를 구해야 하는 문제다. 문자열을 찾기만 하면 되는 것이 아닌 범위를 찾아야 하기 때문에 finish에는 true 대신 문자열의 길이를 넣어주고, 트라이를 구성할 때 실패함수의 finish와 비교해 더 큰 값으로 넣어준다(작은 값은 어차피 중복되므로). 일치하는 문자열을 찾을 때마다 길이를 이용해 해당 구간을 벡터에 넣고, 탐색이 끝난 뒤 스위핑을 이용해 벡터에 존재하는 구간들의 합 길이를 구하면 된다.

 

문제의 입력 조건 때문에 go를 26크기의 배열로 선언하면 메모리 초과가 나서 map으로 선언하였는데, 찾아보니 포인터형 트라이 대신 다음 노드를 int형으로 저장하는 배열형 트라이가 있다고 한다(네트워크 플로우에서 역방향 간선을 포인터 대신 인덱스를 저장해 int형으로 바꿨던 것처럼). 배열형 트라이를 썼다면 메모리가 충분히 허용 범위 안으로 들어왔을 것 같다.

 

 

 

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

struct Trie {
  int finish= 0;
  vector<pair<char, Trie*>> go;
  Trie* fail;
  ~Trie() { for(auto &it:go)  delete it.second; }

  void insert(string_view s){
    Trie* cur= this;

    for(char c:s){
      bool exist= false;

      for(auto &it:cur->go){
        if(it.first==c){
          exist= true;
          cur= it.second;
          
          break;
        }
      }

      if(!exist){
        cur->go.push_back({c, new Trie});
        cur= cur->go.back().second;
      }
    }

    cur->finish= s.length();
  }

  int find(string_view s){
    Trie* cur= this;
    vector<pair<int,int>> v;

    for(int i=0;i<s.length();i++){
      while(1){
        bool exist= false;

        for(auto &it:cur->go){
          if(it.first==s[i]){
            exist= true;
            cur= it.second;
            break;
          }
        }

        if(exist || cur==this)  break;
        cur= cur->fail;
      }

      if(cur->finish){
        v.push_back({i-cur->finish+1, i+1});
      }
    }

    sort(v.begin(), v.end());

    int sz= v.size(), left= -1, right= -1, res=0;
    for(int i=0;i<sz;i++){
      if(right<v[i].first){
        res+= right-left;
  
        left= v[i].first;
        right= v[i].second;
      }else if(right<v[i].second){
        right= v[i].second;
      }
    }
    res+= right-left;

    return res;
  }
  
  void init(){
    Trie* root= this;
    queue<Trie*> q;
    root->fail= root;
    q.push(root);
    
    while(!q.empty()){
      Trie* now= q.front();
      q.pop();
      
      for(auto &it:now->go){
        char x= it.first;
        Trie* next= it.second;
        
        if(next==nullptr)  continue;
        
        if(now==root){
          next->fail= root;
        }else{
          Trie* dest= now->fail;
          
          while(1){
            bool exist= false;
            
            for(auto &it2:dest->go){
              if(it2.first==it.first){
                exist= true;
                dest= it2.second;
                
                break;
              }
            }
            
            if(exist||dest==root)  break;
            
            dest= dest->fail;
          }
          
          next->fail= dest;
        }
        
        if(next->fail->finish)  next->finish= max(next->finish, next->fail->finish);
        
        q.push(next);
      }
    }
  }
};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int n, m;
  string street;
  Trie* trie= new Trie;

  cin >> n >> street >> m;

  while(m--){
    string tile;

    cin >> tile;

    trie->insert(tile);
  }

  trie->init();

  cout << n-trie->find(street) << "\n";

  delete trie;
  return 0;
}

 

 

 

이 문제는 접미사 배열로도 풀 수 있는데, 접미사 배열은 사전 순으로 정렬되어있다는 특성 상 어떤 접두사가 있다면 항상 접미사 배열의 연속적인 구간에 존재할 것이다. 이 범위를 이분탐색으로 찾으면 된다. 이 범위는 접미사 배열을 기준으로 정리되어 있으므로 스위핑을 통해 원본 문자열 기준 범위로 바꿔줘야 하고(나이브하게 바꿔주면 특정 케이스에 시간초과가 나는 것으로 알고 있음) 원본 기준 범위는 아호코라식 풀이처럼 다시 스위핑으로 구간의 길이를 구해주면 된다.

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<pair<int, int>, int> pp;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int n;
  string s;

  cin >> n >> s;

  int d= 1, n2= max(27, n+1);
  vector<int> sfx(n), cnt(n2), idx(n), g(n), tg(n), lcp(n);

  for(int i=0;i<n;i++){
    sfx[i]= i;
    g[i]= s[i]-'a'+1;
  }

  while(1){
    fill_n(cnt.begin(), n2, 0);
    for(int i=0;i<n;i++)  cnt[i+d<n?g[i+d]:0]++;
    for(int i=1;i<n2;i++)  cnt[i]+= cnt[i-1];
    for(int i=n-1;i>=0;i--)  idx[--cnt[i+d<n?g[i+d]:0]]= i;
    
    fill_n(cnt.begin(), n2, 0);
    for(int i=0;i<n;i++)  cnt[g[i]]++;
    for(int i=1;i<n2;i++)  cnt[i]+= cnt[i-1];
    for(int i=n-1;i>=0;i--)  sfx[--cnt[g[idx[i]]]]= idx[i];

    tg[sfx[0]]= 1;
    for(int i=1;i<n;i++){
      int curr= sfx[i], prev= sfx[i-1];
      
      bool same= g[curr]==g[prev] && ((curr+d<n?g[curr+d]:0) == (prev+d<n?g[prev+d]:0));
      
      tg[curr]= tg[prev]+!same;
    }

    g= tg;

    if(g[sfx[n-1]]==n)  break;
    d<<= 1;
  }

  auto cmp2= [] (const pp &A, const pp &B)->bool{
    if(A.first.first!=B.first.first)  return A.first.first>B.first.first;
    return A.second>B.second;
  };
  priority_queue<pp, vector<pp>, decltype(cmp2)> pq(cmp2);

  auto find= [&] (string &str, int len){
    int lo= -1, hi= n-1;
    while(lo+1<hi){
      int mid= (lo+hi+1)/2;
      
      (s.compare(sfx[mid], len, str)<0 ? lo : hi)= mid;
    }
    
    int val1= hi;
    
    if(s.compare(sfx[val1], len, str))  return;

    lo= val1, hi= n;
    while(lo+1<hi){
      int mid= (lo+hi)/2;
      
      (s.compare(sfx[mid], len, str)==0 ? lo : hi)= mid;
    }

    pq.push({{val1, lo}, len});
  };

  int m;

  cin >> m;

  while(m--){
    string t;
    
    cin >> t;

    find(t, t.length());
  }

  vector<pair<int, int>> v2;

  int nows= -1;
  while(!pq.empty()){
    pp nowpq= pq.top();
    nows= max(nows, nowpq.first.first);
    int nowe= nowpq.first.second;
    int nowl= nowpq.second;
    pq.pop();

    while(!pq.empty() && nows==pq.top().first.first){
      nowpq= pq.top();
      if(nowpq.first.second<nowe){
        pq.push({{nowpq.first.second+1, nowe}, nowl});
        nowe= nowpq.first.second;
        nowl= nowpq.second;
      }
      pq.pop();
    }
    
    if(pq.top().first.second<nowe){
      pq.push({{pq.top().first.second+1, nowe}, nowl});
    }

    while(nows<=nowpq.first.second && (pq.empty() || nows<pq.top().first.first)){
      v2.push_back({sfx[nows], sfx[nows]+nowpq.second});
      nows++;
    }
  }

  sort(v2.begin(), v2.end());
  int left= -1, right= -1, res=0;
  for(int i=0,sz2=v2.size();i<sz2;i++){
    if(right<v2[i].first){
      res+= right-left;
      left= v2[i].first;
      right= v2[i].second;
    }else if(right<v2[i].second){
      right= v2[i].second;
    }
  }
  res+= right-left;

  cout << n-res;

  return 0;
}