daily pastebin goal
16%
SHARE
TWEET

Aho-Corasick alg

rmq Oct 21st, 2013 2,927 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cstring>
  3. #include <vector>
  4. using namespace std;
  5. const int k=26,NMAX=10000;
  6. struct bohr_vrtx{
  7.    int next_vrtx[k],pat_num,suff_link,auto_move[k],par,suff_flink;
  8.    bool flag;
  9.    char symb;
  10. };
  11. vector<bohr_vrtx> bohr;
  12. vector<string> pattern;
  13. bohr_vrtx make_bohr_vrtx(int p,char c){
  14.    bohr_vrtx v;
  15.    memset(v.next_vrtx, 255, sizeof(v.next_vrtx));
  16.    memset(v.auto_move, 255, sizeof(v.auto_move));
  17.    v.flag=false;
  18.    v.suff_link=-1;
  19.    v.par=p;
  20.    v.symb=c;
  21.    v.suff_flink=-1;
  22.    return v;
  23. }
  24. void bohr_ini(){
  25.    bohr.push_back(make_bohr_vrtx(0,'$'));
  26. }
  27. void add_string_to_bohr(const string& s){
  28.    int num=0;
  29.    for (int i=0; i<s.length(); i++){
  30.       char ch=s[i]-'a';
  31.       if (bohr[num].next_vrtx[ch]==-1){
  32.          bohr.push_back(make_bohr_vrtx(num,ch));
  33.          bohr[num].next_vrtx[ch]=bohr.size()-1;
  34.          }
  35.       num=bohr[num].next_vrtx[ch];
  36.    }
  37.    bohr[num].flag=true;
  38.    pattern.push_back(s);
  39.    bohr[num].pat_num=pattern.size()-1;
  40. }
  41. bool is_string_in_bohr(const string& s){
  42.    int num=0;
  43.    for (int i=0; i<s.length(); i++){
  44.       char ch=s[i]-'a';
  45.       if (bohr[num].next_vrtx[ch]==-1){
  46.          return false;
  47.          }
  48.       num=bohr[num].next_vrtx[ch];
  49.    }
  50.    return true;
  51. }
  52. int get_auto_move(int v, char ch);
  53. int get_suff_link(int v){
  54.    if (bohr[v].suff_link==-1)
  55.       if (v==0||bohr[v].par==0)
  56.          bohr[v].suff_link=0;
  57.       else
  58.          bohr[v].suff_link=get_auto_move(get_suff_link(bohr[v].par), bohr[v].symb);
  59.    return bohr[v].suff_link;
  60. }
  61. int get_auto_move(int v, char ch){
  62.    if (bohr[v].auto_move[ch]==-1)
  63.       if (bohr[v].next_vrtx[ch]!=-1)
  64.          bohr[v].auto_move[ch]=bohr[v].next_vrtx[ch];
  65.       else
  66.          if (v==0)
  67.             bohr[v].auto_move[ch]=0;
  68.          else
  69.             bohr[v].auto_move[ch]=get_auto_move(get_suff_link(v), ch);
  70.    return bohr[v].auto_move[ch];
  71. }
  72. int get_suff_flink(int v){
  73.    if (bohr[v].suff_flink==-1){
  74.       int u=get_suff_link(v);
  75.       if (u==0)
  76.          bohr[v].suff_flink=0;
  77.       else
  78.          bohr[v].suff_flink=(bohr[u].flag)?u:get_suff_flink(u);
  79.    }
  80.    return bohr[v].suff_flink;
  81. }
  82. void check(int v,int i){
  83.     for(int u=v;u!=0;u=get_suff_flink(u)){
  84.         if (bohr[u].flag) cout<<i-pattern[bohr[u].pat_num].length()+1<<" "<<pattern[bohr[u].pat_num]<<endl;
  85.     }
  86. }
  87. void find_all_pos(const string& s){
  88.     int u=0;
  89.     for(int i=0;i<s.length();i++){
  90.         u=get_auto_move(u,s[i]-'a');
  91.         check(u,i+1);
  92.     }
  93. }
  94. int main(){
  95.    //...
  96.    bohr_ini();
  97. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top