peltorator

Ахо-Корасик

Jun 18th, 2017
179
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. struct aho
  2. {
  3.     vector<vector<int> > g, gr;
  4.     vector<string> str;
  5.     int root;
  6.     int sz;
  7.     vector<ll> ending;
  8.     vector<int> link;
  9.     char firstlet;
  10.     int numlet = 0;
  11.  
  12.     aho():
  13.         g(),
  14.         gr(),
  15.         str(),
  16.         root(0),
  17.         sz(0),
  18.         ending(),
  19.         link() {}
  20.  
  21.     aho(vector<string> q, char firlet = 'a') // change
  22.     {
  23.         firstlet = firlet;
  24.         sz = q.size();
  25.         str = q;
  26.         g.clear();
  27.         gr.clear();
  28.         ending.clear();
  29.         link.clear();
  30.         root = 0;
  31.         ending.assign(1, 0);
  32.         numlet = 0;
  33.         for (int i = 0; i < q.size(); i++)
  34.             for (int j = 0; j < q[i].size(); j++)
  35.                 numlet = max(numlet, q[i][j] - firstlet);
  36.         numlet++;
  37.         g.push_back(vector<int>(numlet, -1));
  38.         for (int i = 0; i < q.size(); i++)
  39.         {
  40.             int v = root;
  41.             for (int j = 0; j < q[i].size(); j++)
  42.             {
  43.                 if (g[v][q[i][j] - firstlet] == -1)
  44.                 {
  45.                     g[v][q[i][j] - firstlet] = g.size();
  46.                     g.push_back(vector<int>(numlet, -1));
  47.                     ending.push_back(0);
  48.                 }
  49.                 v = g[v][q[i][j] - firstlet];
  50.             }
  51.             ending[v]++;
  52.         }
  53.         link.assign(g.size(), -1);
  54.         link[root] = root;
  55.         queue<int> que;
  56.         que.push(root);
  57.         while (que.size())
  58.         {
  59.             int v = que.front();
  60.             que.pop();
  61.             for (int i = 0; i < numlet; i++)
  62.                 if (g[v][i] == -1)
  63.                 {
  64.                     if (v == root)
  65.                         g[v][i] = v;
  66.                     else
  67.                         g[v][i] = g[link[v]][i];
  68.                 }
  69.                 else
  70.                 {
  71.                     que.push(g[v][i]);
  72.                     if (v == root)
  73.                         link[g[v][i]] = v;
  74.                     else
  75.                         link[g[v][i]] = g[link[v]][i];
  76.                 }
  77.         }
  78.         gr.resize(g.size());
  79.         for (int i = 0; i < g.size(); i++)
  80.             if (i != root)
  81.                 gr[link[i]].push_back(i);
  82.         dfslink(root);
  83.     }
  84.  
  85.     void dfslink(int v)
  86.     {
  87.         for (int u : gr[v])
  88.         {
  89.             ending[u] += ending[v];
  90.             dfslink(u);
  91.         }
  92.     }
  93.  
  94.     ll find(string s) // change
  95.     {
  96.         ll ans = 0;
  97.         int v = root;
  98.         for (int i = 0; i < s.size(); i++)
  99.         {
  100.             v = g[v][s[i] - firstlet];
  101.             ans += ending[v];
  102.         }
  103.         return ans;
  104.     }
  105. };
RAW Paste Data