string/ahocorasick.cpp

• View this file on GitHub
• Last update: 2021-01-22 18:37:50+09:00

Depends on

• string/trie.cpp

Verified with

• test/aoj/2212.test.cpp
• test/aoj/2257.test.cpp
• test/aoj/3073.test.cpp
• test/yukicoder/1013.test.cpp

Code

#ifndef call_from_test
#include<bits/stdc++.h>
using namespace std;

#define call_from_test
#include "trie.cpp"
#undef call_from_test

#endif
//BEGIN CUT HERE
template<size_t X, bool heavy>
struct AhoCorasick : Trie<X+1>{
  using super = Trie<X+1>;
  using super::super, super::next, super::size;
  using super::vs, super::conv;

  vector<int> cnt,ord;

  // O(\sigma \sum |T_i|)
  void build(){
    int n=vs.size();
    cnt.resize(n);
    for(int i=0;i<n;i++){
      if(heavy) sort(vs[i].idxs.begin(),vs[i].idxs.end());
      cnt[i]=vs[i].idxs.size();
    }

    queue<int> que;
    for(int i=0;i<(int)X;i++){
      if(~next(0,i)){
        next(next(0,i),X)=0;
        que.emplace(next(0,i));
      }else{
        next(0,i)=0;
      }
    }

    while(!que.empty()){
      ord.emplace_back(que.front());
      auto &x=vs[que.front()];
      int fail=x.nxt[X];

      cnt[que.front()]+=cnt[fail];
      que.pop();

      for(int i=0;i<(int)X;i++){
        int &nx=x.nxt[i];
        if(nx<0){
          nx=next(fail,i);
          continue;
        }
        que.emplace(nx);
        next(nx,X)=next(fail,i);
        if(heavy){
          auto &idx=vs[nx].idxs;
          auto &idy=vs[next(fail,i)].idxs;
          vector<int> idz;
          set_union(idx.begin(),idx.end(),
                    idy.begin(),idy.end(),
                    back_inserter(idz));
          idx=idz;
        }
      }
    }
    reverse(ord.begin(),ord.end());
  }

  int count(int pos){
    return cnt[pos];
  }

  // O(|S|)
  long long match(string s){
    long long res=0;
    int pos=0;
    for(auto &c:s){
      pos=next(pos,conv(c));
      res+=count(pos);
    }
    return res;
  }

  // O(|S| + \sum |T_i|)
  vector<int> frequency(string s){
    vector<int> res(size(),0);
    int pos=0;
    for(auto &c:s){
      pos=next(pos,conv(c));
      res[pos]++;
    }
    for(int p:ord)
      res[vs[p].nxt[X]]+=res[p];
    return res;
  }
};
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.11.3/x64/lib/python3.11/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.11.3/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
  File "/opt/hostedtoolcache/Python/3.11.3/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 400, in update
    raise BundleErrorAt(path, i + 1, "unable to process #include in #if / #ifdef / #ifndef other than include guards")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: string/ahocorasick.cpp: line 6: unable to process #include in #if / #ifdef / #ifndef other than include guards

Back to top page